Given a complete undirected graph with the nodes partitioned into m node sets called clusters, the Generalized Minimum Spanning Tree problem denoted by GMST is to find a minimum-cost tree which includes exactly one node from each cluster. It is known that the GMST problem is NP-hard and even finding a near optimal solution is NP-hard. We give an approximation algorithm for the Generalized Minimum Spanning Tree problem in the case when the cluster size is bounded by $\rho$. In this case, the GMST problem can be approximated to within 2$\rho$.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||9|
|Publication status||Published - 2001|
|Name||Memorandum / Department of Applied Mathematics|
|Publisher||Department of Applied Mathematics, University of Twente|
Pop, P. C., Kern, W., & Still, G. J. (2001). An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. (Memorandum / Department of Applied Mathematics; No. 1577). Enschede: University of Twente, Department of Applied Mathematics.