  Let G=(V,E) be a connected graph, where V and E represent, respectively, the
node-set and the edge-set. Besides, let Q \subseteq V be a set of terminal
nodes, and r \in Q be the root node of the graph. Given a weight c_{ij} \in
\mathbb{N} associated to each edge (i,j) \in E, the Steiner Tree Problem in
graphs (STP) consists in finding a minimum-weight subgraph of G that spans all
nodes in Q. In this paper, we consider the Min-max Regret Steiner Tree Problem
with Interval Costs (MMR-STP), a robust variant of STP. In this variant, the
weight of the edges are not known in advance, but are assumed to vary in the
interval [l_{ij}, u_{ij}]. We develop an ILP formulation, an exact algorithm,
and three heuristics for this problem. Computational experiments, performed on
generalizations of the classical STP instances, evaluate the efficiency and the
limits of the proposed methods.
