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

DOI10.1016/J.DAM.2017.03.010zbMATH Open1361.05038OpenAlexW2606584551MaRDI QIDQ528561FDOQ528561

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

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

zbMATH Keywords

shortest pathsfacetsliftinghop constraintsjump inequalities

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Shortest Path Problems with Resource Constraints
• Algorithms for finding paths with multiple constraints
• Title not available (Why is that?)
• Notes on polyhedra associated with hop-constrained paths
• A branch and cut approach to the cardinality constrained circuit problem.
• 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 a Hop-Constrained Model to Generate Alternative Communication Network Design
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Title not available (Why is that?)
• Linear programming: foundations and extensions
• 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
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• On the Linear Description of the k-cycle Polytope
• Facets of the \(p\)-cycle polytope
• On the facets and diameter of thek-cycle polytope
• The Fixed-Outdegree 1-Arborescence Polytope
• Title not available (Why is that?)
• Characterization of facets of the hop constrained chain polytope via dynamic programming

Cited In (3)

• PSO based constraint optimization of intuitionistic fuzzy shortest path problem in an undirected network
• On the directed hop-constrained shortest path problem
• A polyhedral study of the diameter constrained minimum spanning tree problem

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)