ILP formulation of the degree-constrained minimum spanning hierarchy problem

DOI10.1007/S10878-017-0159-4MaRDI QIDQ1631637zbMATH OpenOpenAlexFDO

Authors Massinissa Merabet, Miklos Molnar, Sylvain Durand

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

DCMSHDCMSTdegree-constrained spanning problemILPinteger linear programmingspanning hierarchyspanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Approximation of the degree-constrained minimum spanning hierarchies
• Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• A strong symmetric formulation for the min-degree constrained minimum spanning tree problem

Cites work

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

Cited in

(1)

• Approximation of the degree-constrained minimum spanning hierarchies

Describes a project that uses

Uses Software

• VRP
• GLPK

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

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