Article ID: | iaor20062253 |
Country: | United Kingdom |
Volume: | 56 |
Issue: | 4 |
Start Page Number: | 382 |
End Page Number: | 389 |
Publication Date: | Apr 2005 |
Journal: | Journal of the Operational Research Society |
Authors: | Dror M., Haouari M., Chaouachi J. |
Keywords: | minimum spanning trees |
We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.