ILP formulation of the degree-constrained minimum spanning hierarchy problem

DOI10.1007/s10878-017-0159-4zbMath1414.90348OpenAlexW2743185899MaRDI QIDQ1631637

Massinissa Merabet, Sylvain Durand, Miklos Molnar

Publication date: 6 December 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01584405/file/JOCO-V3_01584405_ILP.pdf

zbMATH Keywords

spanning treeinteger linear programmingILPDCMSHDCMSTdegree-constrained spanning problemspanning hierarchy

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Uses Software

• GLPK
• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Integer programming and combinatorial optimization. 18th international conference, IPCO 2016, Liège, Belgium, June 1--3, 2016. Proceedings
• Bounded-degree spanning tree problems: models and new algorithms
• A cutting plane procedure for the travelling salesman problem on road networks
• Homomorphisms to oriented paths
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• Approximating minimum bounded degree spanning trees to within one of optimal
• The traveling salesman problem on a graph and some related integer polyhedra
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• A fundamental problem in vehicle routing
• Many birds with one stone
• Approximation of the Degree-Constrained Minimum Spanning Hierarchies
• Spanning tree manipulation and the travelling salesman problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• A comparison of Steiner tree relaxations
• Comparison of algorithms for the degree constrained minimum spanning tree

This page was built for publication: ILP formulation of the degree-constrained minimum spanning hierarchy problem