Return to results
Journal articles (2020), Discrete Applied Mathematics, 285, pp. 364-379

A polyhedral study of the diameter constrained minimum spanning tree problem

GOUVEIA Luis, LEITNER Markus, LJUBIC Ivana

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. Link to the article

LEITNER, M., GOUVEIA, L. and LJUBIC, I. (2020). A polyhedral study of the diameter constrained minimum spanning tree problem. Discrete Applied Mathematics, 285, pp. 364-379.

Keywords : #Integer-programming,-Diameter-constrained-trees,-Facet