Abstract

The tree-spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree -spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem.