The generalized minimum spanning tree polytope and related polytopes

P.C. Pop

Research output: Book/ReportReportOther research output

37 Downloads (Pure)


The Generalized Minimum Spanning Tree problem denoted by GMST is a variant of the classical Minimum Spanning Tree problem in which nodes are partitioned into clusters and the problem calls for a minimum cost tree spanning at least one node from each cluster. A different version of the problem, called E-GMST arises when exactly one node from each cluster has to be visited. Both GMST problem and E-GMST problem are NP-hard problems. In this paper, we model GMST problem and E-GMST problem as integer linear programs and study the facial structure of the corresponding polytopes.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages9
Publication statusPublished - 2001

Publication series

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


  • MSC-05C05
  • MSC-90C11
  • IR-65774
  • MSC-90B10
  • EWI-3407
  • MSC-90C27


Dive into the research topics of 'The generalized minimum spanning tree polytope and related polytopes'. Together they form a unique fingerprint.

Cite this