An Approximation Algorithm for the Generalized Minimum Spanning Tree Problem with Bounded Cluster Size.
Petrică C. Pop, Walter Kern, Georg Still · University of Twente Research Information · 2001
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$.