### Abstract

Original language | English |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 9 |

Publication status | Published - 2001 |

### Publication series

Name | Memorandum / Department of Applied Mathematics |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1577 |

ISSN (Print) | 0169-2690 |

### Fingerprint

### Keywords

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

### Cite this

*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.

}

*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.

Research output: Book/Report › Report › Other 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 -