On the directed hop-constrained shortest path problem

DOI10.1016/S0167-6377(03)00026-9zbMATH Open1056.90116OpenAlexW2006877095MaRDI QIDQ1433652FDOQ1433652

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

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

zbMATH Keywords

Valid inequalitiesHop-constrained pathsPolyhedral characterizations

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Title not available (Why is that?)
• Notes on polyhedra associated with hop-constrained paths
• 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?)

Cited In (18)

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

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)