The generalized minimum spanning tree polytope and related polytopes

P.C. Pop

Research output: Book/ReportReportOther research output

15 Downloads (Pure)

Abstract

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

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

Keywords

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

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

  • Cite this

    Pop, P. C. (2001). The generalized minimum spanning tree polytope and related polytopes. (Memorandum; No. 1587). Enschede: University of Twente, Department of Applied Mathematics.