@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",
number = "1577",
address = "Netherlands",
}