A new relaxation method for the generalized minimum spanning tree problem

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

doi:10.1016/j.ejor.2004.07.058

A new relaxation method for the generalized minimum spanning tree problem

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

30 Citations (Scopus)

16 Downloads (Pure)

Abstract

We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is -hard. We present several mixed integer programming formulations of the problem. Based on a new formulation of the problem we give a new solution procedure that finds the optimal solution of the GMST problem for graphs with nodes up to 240. We discuss the advantages of our approach in comparison with earlier methods.

Original language	English
Pages (from-to)	900-908
Number of pages	9
Journal	European journal of operational research
Volume	170
Issue number	3
DOIs	https://doi.org/10.1016/j.ejor.2004.07.058
Publication status	Published - 1 May 2006

Access to Document

10.1016/j.ejor.2004.07.058

Cite this

@article{324aec1717434d1d8a53838aeebd7890,

title = "A new relaxation method for the generalized minimum spanning tree problem",

abstract = "We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is -hard. We present several mixed integer programming formulations of the problem. Based on a new formulation of the problem we give a new solution procedure that finds the optimal solution of the GMST problem for graphs with nodes up to 240. We discuss the advantages of our approach in comparison with earlier methods.",

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

year = "2006",

month = may,

day = "1",

doi = "10.1016/j.ejor.2004.07.058",

language = "English",

volume = "170",

pages = "900--908",

journal = "European journal of operational research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A new relaxation method for the generalized minimum spanning tree problem

AU - Pop, Petricia C.

AU - Kern, Walter

AU - Still, Georg J.

PY - 2006/5/1

Y1 - 2006/5/1

N2 - We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is -hard. We present several mixed integer programming formulations of the problem. Based on a new formulation of the problem we give a new solution procedure that finds the optimal solution of the GMST problem for graphs with nodes up to 240. We discuss the advantages of our approach in comparison with earlier methods.

AB - We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is -hard. We present several mixed integer programming formulations of the problem. Based on a new formulation of the problem we give a new solution procedure that finds the optimal solution of the GMST problem for graphs with nodes up to 240. We discuss the advantages of our approach in comparison with earlier methods.

U2 - 10.1016/j.ejor.2004.07.058

DO - 10.1016/j.ejor.2004.07.058

M3 - Article

SN - 0377-2217

VL - 170

SP - 900

EP - 908

JO - European journal of operational research

JF - European journal of operational research

IS - 3

ER -

A new relaxation method for the generalized minimum spanning tree problem

Abstract

Access to Document

Fingerprint

Cite this