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

21 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

Fingerprint

Minimum Spanning Tree
Approximation Algorithms
NP-complete problem
Vertex of a graph
Undirected Graph
Complete Graph
Optimal Solution
Costs

Keywords

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

Cite this

Pop, P. C., Kern, W., & Still, G. J. (2001). An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. (Memorandum / Department of Applied Mathematics; No. 1577). Enschede: University of Twente, Department of Applied Mathematics.
Pop, P.C. ; Kern, W. ; Still, G.J. / An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. Enschede : University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum / Department of Applied Mathematics; 1577).
@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",

}

Pop, PC, Kern, W & Still, GJ 2001, An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. Memorandum / Department of Applied Mathematics, no. 1577, University of Twente, Department of Applied Mathematics, Enschede.

An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. / Pop, P.C.; Kern, W.; Still, G.J.

Enschede : University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum / Department of Applied Mathematics; No. 1577).

Research output: Book/ReportReportOther research output

TY - BOOK

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

AU - Pop, P.C.

AU - Kern, W.

AU - Still, G.J.

N1 - Imported from MEMORANDA

PY - 2001

Y1 - 2001

N2 - 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$.

AB - 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$.

KW - MSC-05C05

KW - MSC-90C11

KW - IR-65764

KW - MSC-90C27

KW - EWI-3397

KW - MSC-90B10

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Pop PC, Kern W, Still GJ. An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. Enschede: University of Twente, Department of Applied Mathematics, 2001. 9 p. (Memorandum / Department of Applied Mathematics; 1577).