Characterization of facets of the hop constrained chain polytope via dynamic programming

DOI10.1016/J.DAM.2013.08.015zbMATH Open1303.90117OpenAlexW2012203419MaRDI QIDQ741741FDOQ741741

Authors: Martin Grötschel, Rüdiger Stephan 

Publication date: 12 September 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2013.08.015

Recommendations

• A complete characterization of jump inequalities for the hop-constrained shortest path problem
• On the directed hop-constrained shortest path problem
• Notes on polyhedra associated with hop-constrained paths
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• A note on hop-constrained walk polytopes.

zbMATH Keywords

dynamic programmingfacetschainshop constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Cites Work

• On a routing problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• On formulations and methods for the hop-constrained minimum spanning tree problem
• Using separation algorithms to generate mixed integer model reformulations
• A branch and cut approach to the cardinality constrained circuit problem.
• Projection, lifting and extended formulation integer and combinatorial optimization
• On cardinality constrained cycle and path polytopes
• Facets of the \((s,t)-p\)-path polytope
• Hop-constrained node survivable network design: An application to MPLS over WDM
• On the directed hop-constrained shortest path problem
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Title not available (Why is that?)
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• A note on hop-constrained walk polytopes.
• Polyhedral Characterization of Discrete Dynamic Programming
• On the Linear Description of the k-cycle Polytope
• Facets of the \(p\)-cycle polytope
• On the facets and diameter of thek-cycle polytope
• Compact vs. exponential-size LP relaxations

Cited In (2)

• A note on hop-constrained walk polytopes.
• A complete characterization of jump inequalities for the hop-constrained shortest path problem

This page was built for publication: Characterization of facets of the hop constrained chain polytope via dynamic programming

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