A polyhedral study of the diameter constrained minimum spanning tree problem

Luis Gouveia, Markus Leitner*, Ivana Ljubić

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

18 Downloads (Pure)

Abstract

This paper provides a first polyhedral study of the diameter constrained minimum spanning tree problem (DMSTP). We introduce a new set of inequalities, the circular-jump inequalities which strengthen the well-known jump inequalities. These inequalities are further generalized in two ways: either by increasing the number of partitions defining a jump, or by combining jumps with cutsets. Most of the proposed new inequalities are shown to define facets of the DMSTP polytope under very mild conditions. Currently best known lower bounds for the DMSTP are obtained from an extended formulation on a layered graph using the concept of central nodes/edges. A subset of the new families of inequalities is shown to be not implied by this layered graph formulation.

Original languageEnglish
Pages (from-to)364-379
Number of pages16
JournalDiscrete Applied Mathematics
Volume285
Early online date20 Jun 2020
DOIs
Publication statusPublished - 15 Oct 2020

Keywords

  • Diameter constrained trees
  • Facet
  • Integer programming

Fingerprint Dive into the research topics of 'A polyhedral study of the diameter constrained minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this