# An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size

P.C. Pop, W. Kern, G.J. Still

Research output: Book/ReportReportOther research output

### Abstract

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$.
Original language English Enschede University of Twente, Department of Applied Mathematics 9 Published - 2001

### Publication series

Name Memorandum / Department of Applied Mathematics Department of Applied Mathematics, University of Twente 1577 0169-2690

• MSC-05C05
• MSC-90C11
• IR-65764
• MSC-90C27
• EWI-3397
• MSC-90B10

### Cite this

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.