The robust spanning tree problem with interval data

Motivated by telecommunications applications we investigate the minimum spanning tree problem where edge costs are interval numbers. Since minimum spanning trees depend on the realization of the edge costs, we define the robust spanning tree problem to hedge against the worst case contingency, and present a mixed integer programming formulation of the problem. We also define some useful optimality concepts, and present characterizations for these entities leading to polynomial time recognition algorithms. These entities are then used to preprocess a given graph with interval data prior to the solution of the robust spanning tree problem. Computational results show that these preprocessing procedures are quite effective in reducing the time to compute a robust spanning tree. © 2001 Elsevier Science B.V. All rights reserved