A note on hop-constrained walk polytopes.

DOI10.1016/j.orl.2003.10.008zbMath1052.05033OpenAlexW2049236593MaRDI QIDQ703241

Njål Foldnes, Geir Dahl, Luís Gouveia

Publication date: 11 January 2005

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

Full work available at URL: https://doi.org/10.1016/j.orl.2003.10.008

zbMATH Keywords

Complete descriptionExtended formulationHop-constraintsWalk

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ Enhancing discretized formulations: the knapsack reformulation and the star reformulation ⋮ The \(k\) edge-disjoint 3-hop-constrained paths polytope ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming

Cites Work

• On the directed hop-constrained shortest path problem
• Notes on polyhedra associated with hop-constrained paths
• The perfectly matchable subgraph polytope of a bipartite graph
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints

This page was built for publication: A note on hop-constrained walk polytopes.