Relaxation methods for the Generalized Minimum Spanning Tree Problem

P.C. Pop; Walter Kern; Georg J. Still

doi:10.1016/S1571-0653(05)80085-X

Relaxation methods for the Generalized Minimum Spanning Tree Problem

P.C. Pop, Walter Kern, Georg J. Still

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

1 Citation (Scopus)

34 Downloads (Pure)

Abstract

Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.

Original language	Undefined
Title of host publication	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Editors	Johann L. Hurink, Stefan Pickl, Haitze J. Broersma, U. Faigle
Publisher	Elsevier
Pages	76-79
DOIs	https://doi.org/10.1016/S1571-0653(05)80085-X
Publication status	Published - 2001
Event	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001 - University of Cologne, Cologne, Germany Duration: 6 Jun 2001 → 8 Jun 2001 Conference number: 1

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
Volume	8

Workshop

Workshop	1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001
Abbreviated title	CTW
Country/Territory	Germany
City	Cologne
Period	6/06/01 → 8/06/01

Keywords

IR-74518

Access to Document

10.1016/S1571-0653(05)80085-X

Cite this

@inbook{b805a38fbc64486dbcf83859e720e6d8,

title = "Relaxation methods for the Generalized Minimum Spanning Tree Problem",

abstract = "Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.",

keywords = "IR-74518",

author = "P.C. Pop and Walter Kern and Still, {Georg J.}",

year = "2001",

doi = "10.1016/S1571-0653(05)80085-X",

language = "Undefined",

series = "Electronic Notes in Discrete Mathematics",

publisher = "Elsevier",

pages = "76--79",

editor = "Hurink, {Johann L.} and Stefan Pickl and Broersma, {Haitze J.} and U. Faigle",

booktitle = "1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization",

note = "1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001 ; Conference date: 06-06-2001 Through 08-06-2001",

}

Pop, PC, Kern, W & Still, GJ 2001, Relaxation methods for the Generalized Minimum Spanning Tree Problem. in JL Hurink, S Pickl, HJ Broersma & U Faigle (eds), 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Electronic Notes in Discrete Mathematics, vol. 8, Elsevier, pp. 76-79, 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001, Cologne, Germany, 6/06/01. https://doi.org/10.1016/S1571-0653(05)80085-X

Relaxation methods for the Generalized Minimum Spanning Tree Problem. / Pop, P.C.; Kern, Walter; Still, Georg J.
1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization. ed. / Johann L. Hurink; Stefan Pickl; Haitze J. Broersma; U. Faigle. Elsevier, 2001. p. 76-79 (Electronic Notes in Discrete Mathematics; Vol. 8).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

T1 - Relaxation methods for the Generalized Minimum Spanning Tree Problem

AU - Pop, P.C.

AU - Kern, Walter

AU - Still, Georg J.

N1 - Conference code: 1

PY - 2001

Y1 - 2001

N2 - Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.

AB - Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.

KW - IR-74518

U2 - 10.1016/S1571-0653(05)80085-X

DO - 10.1016/S1571-0653(05)80085-X

M3 - Chapter

T3 - Electronic Notes in Discrete Mathematics

SP - 76

EP - 79

BT - 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization

A2 - Hurink, Johann L.

A2 - Pickl, Stefan

A2 - Broersma, Haitze J.

A2 - Faigle, U.

PB - Elsevier

T2 - 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001

Y2 - 6 June 2001 through 8 June 2001

ER -