Relaxation methods for the Generalized Minimum Spanning Tree Problem

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

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

1 Citation (Scopus)

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 languageUndefined
Title of host publication1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization
EditorsJohann L. Hurink, Stefan Pickl, Haitze J. Broersma, U. Faigle
PublisherElsevier
Pages76-79
DOIs
Publication statusPublished - 2001
Event1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001 - University of Cologne, Cologne, Germany
Duration: 6 Jun 20018 Jun 2001
Conference number: 1

Publication series

NameElectronic Notes in Discrete Mathematics
PublisherElsevier
Volume8

Workshop

Workshop1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2001
Abbreviated titleCTW
CountryGermany
CityCologne
Period6/06/018/06/01

Keywords

  • IR-74518

Cite this