On the directed hop-constrained shortest path problem

DOI10.1016/S0167-6377(03)00026-9MaRDI QIDQ1433652zbMATHOpenAlexFDO

Authors Geir Dahl, Luis Gouveia

Publication date 1 July 2004

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(03)00026-9

zbMATH Keywords

Valid inequalitiesHop-constrained pathsPolyhedral characterizations

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• The Directed Disjoint Shortest Paths Problem
• Efficient construction of directed hopsets and parallel approximate shortest paths
• Fast approximation algorithms for routing problems with hop-wise constraints
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 30302
• A complete characterization of jump inequalities for the hop-constrained shortest path problem
• A note on the constrained shortest-path problem
• On dynamic shortest paths problems
• Algorithms – ESA 2004
• On an exact method for the constrained shortest path problem

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Notes on polyhedra associated with hop-constrained paths
• 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

(18)

• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• A polyhedral study of the diameter constrained minimum spanning tree problem
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• A note on hop-constrained walk polytopes.
• Container shipping service selection and cargo routing with transshipment limits
• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• Characterization of facets of the hop constrained chain polytope via dynamic programming
• The \(k\) edge-disjoint 3-hop-constrained paths polytope
• Optimal network design with end-to-end service requirements
• On cardinality constrained cycle and path polytopes
• Parameterized complexity of length-bounded cuts and multicuts
• Facets of the \((s,t)-p\)-path polytope
• The Directed Disjoint Shortest Paths Problem
• Composition of graphs and the hop-constrained path problem
• Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
• A complete characterization of jump inequalities for the hop-constrained shortest path problem
• Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope

This page was built for publication: On the directed hop-constrained shortest path problem

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