The generalized minimum spanning tree problem

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

Research output: Book/ReportReportOther research output

162 Downloads (Pure)

Abstract

We consider the Generalized Minimum Spanning Tree Problem denoted by GMSTP. It is known that GMSTP is NP-hard and even finding a near optimal solution is NP-hard. We introduce a new mixed integer programming formulation of the problem which contains a polynomial number of constraints and a polynomial number of variables. Based on this formulation we give an heuristic solution, a lower bound procedure and an upper bound procedure and present the advantages of our approach in comparison with an earlier method. We present a solution procedure for solving GMST problem using cutting planes.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2000

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1542
ISSN (Print)0169-2690

Keywords

  • MSC-90C11
  • IR-65729
  • EWI-3362
  • MSC-90C35

Cite this

Pop, P. C., Kern, W., & Still, G. J. (2000). The generalized minimum spanning tree problem. Enschede: University of Twente, Department of Applied Mathematics.