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

27 Downloads (Pure)

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 languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages9
Publication statusPublished - 2001

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
No.1577
ISSN (Print)0169-2690

Keywords

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

Fingerprint Dive into the research topics of 'An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size'. Together they form a unique fingerprint.

Cite this