An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size
Pop, P.C. and Kern, W. and Still, G.J. (2001) An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. [Report]

PDF
135kB 
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 minimumcost tree which includes exactly one node from each cluster. It is known that the GMST problem is NPhard and even finding a near optimal solution is NPhard. We give an approximation algorithm for the Generalized Minimum Spanning Tree problem in the case when the cluster size is bounded by . In this case, the GMST problem can be approximated to within 2. 
Item Type:  Report 
Additional information:  Imported from MEMORANDA 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65764 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page