A new relaxation method for the generalized minimum spanning tree problem

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

Research output: Contribution to journalArticleAcademicpeer-review

28 Citations (Scopus)

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 languageEnglish
Pages (from-to)900-908
Number of pages9
JournalEuropean journal of operational research
Volume170
Issue number3
DOIs
Publication statusPublished - 1 May 2006

Fingerprint Dive into the research topics of 'A new relaxation method for the generalized minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this