@book{78d687bdeae9468ba5933aa6bdf53103,

title = "An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size",

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$.",

keywords = "MSC-05C05, MSC-90C11, IR-65764, MSC-90C27, EWI-3397, MSC-90B10",

author = "P.C. Pop and W. Kern and G.J. Still",

note = "Imported from MEMORANDA",

year = "2001",

language = "English",

series = "Memorandum / Department of Applied Mathematics",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1577",

}