A complete characterization of jump inequalities for the hop-constrained shortest path problem

DOI10.1016/J.DAM.2017.03.010MaRDI QIDQ528561zbMATH OpenOpenAlexFDO

Authors Wolfgang F. Riedl

Publication date 12 May 2017

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

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

zbMATH Keywords

shortest pathsfacetsliftinghop constraintsjump inequalities

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• On the directed hop-constrained shortest path problem
• Characterization of facets of the hop constrained chain polytope via dynamic programming
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• Notes on polyhedra associated with hop-constrained paths
• The k edge-disjoint 3-hop-constrained paths polytope

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• scientific article; zbMATH DE number 1517142 (Why is no real title available?)
• A branch and cut approach to the cardinality constrained circuit problem.
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• A note on hop-constrained walk polytopes.
• Algorithms for finding paths with multiple constraints
• Characterization of facets of the hop constrained chain polytope via dynamic programming
• Facets of the \((s,t)-p\)-path polytope
• Facets of the \(p\)-cycle polytope
• Hop-constrained node survivable network design: An application to MPLS over WDM
• Linear programming: foundations and extensions
• Notes on polyhedra associated with hop-constrained paths
• On cardinality constrained cycle and path polytopes
• On formulations and methods for the hop-constrained minimum spanning tree problem
• On the Linear Description of the k-cycle Polytope
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• On the directed hop-constrained shortest path problem
• On the facets and diameter of thek-cycle polytope
• Polyhedral Characterization of Discrete Dynamic Programming
• Shortest Path Problems with Resource Constraints
• The Fixed-Outdegree 1-Arborescence Polytope
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Using a Hop-Constrained Model to Generate Alternative Communication Network Design

Cited in

(5)

• A polyhedral study of the diameter constrained minimum spanning tree problem
• On the directed hop-constrained shortest path problem
• Characterization of facets of the hop constrained chain polytope via dynamic programming
• Composition of graphs and the hop-constrained path problem
• PSO based constraint optimization of intuitionistic fuzzy shortest path problem in an undirected network

This page was built for publication: A complete characterization of jump inequalities for the hop-constrained shortest path problem

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