Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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

Share/Save/Bookmark

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]

[img]
Preview
PDF
132Kb
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$.
Item Type:Report
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