A polyhedral study of the diameter constrained minimum spanning tree problem

DOI10.1016/J.DAM.2020.05.020MaRDI QIDQ2197445zbMATH OpenOpenAlexFDO

Authors Markus Leitner, Ivana Ljubić, Luis Gouveia

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://research.vu.nl/en/publications/0fd99c6e-e540-48bd-af1a-80e0d16c2087

zbMATH Keywords

diameter constrained treesfacetinteger programming

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• The two-level diameter constrained spanning tree problem
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
• A hybrid heuristic for the diameter constrained minimum spanning tree problem
• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem

Cites work

• A catalog of steiner tree formulations
• A complete characterization of jump inequalities for the hop-constrained shortest path problem
• An analytical comparison of different formulations of the travelling salesman problem
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Notes on polyhedra associated with hop-constrained paths
• On formulations and methods for the hop-constrained minimum spanning tree problem
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• On the directed hop-constrained shortest path problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The k edge-disjoint 3-hop-constrained paths polytope
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• Using a Hop-Constrained Model to Generate Alternative Communication Network Design

Cited in

(5)

• A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
• Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees
• A hybrid heuristic for the diameter constrained minimum spanning tree problem
• The two-level diameter constrained spanning tree problem
• Polyhedral studies for minimum‐span graph labelling with integer distance constraints

This page was built for publication: A polyhedral study of the diameter constrained minimum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197445)