Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

0.00 Avg rating0 Votes
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: , ,
Keywords: minimum spanning trees
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.