Relaxation methods for the Generalized Minimum Spanning Tree Problem

Share/Save/Bookmark

Pop, P.C. and Kern, W. and Still, G. and Faigle, U. (2001) Relaxation methods for the Generalized Minimum Spanning Tree Problem. In: 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Electronic Notes in Discrete Mathematics, 8 . Elsevier, pp. 76-79.

[img] PDF
Restricted to UT campus only

153kB
Abstract:Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.
Item Type:Book Section
Copyright:© 2001 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74518
Official URL:http://dx.doi.org/10.1016/S1571-0653(05)80085-X
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page