The generalized minimum spanning tree problem

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

Research output: Book/ReportReportOther research output

250 Downloads (Pure)


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

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


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

Cite this