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

M. Haouari, J. Chaouachi, M. Dror

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)382-389
Number of pages8
JournalJournal of the Operational Research Society
Issue number4
StatePublished - Apr 2005


  • Branch-and-bound: Lagrangian relaxation
  • Minimum spanning tree

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing


Dive into the research topics of 'Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm'. Together they form a unique fingerprint.

Cite this