On the \(k\) edge-disjoint 2-hop-constrained paths polytope

DOI10.1016/j.orl.2005.09.001zbMath1152.90661OpenAlexW2053469491MaRDI QIDQ2480058

Geir Dahl, David Huygens, Pierre Pesneau, Ali Ridha Mahjoub

Publication date: 28 March 2008

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

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

zbMATH Keywords

polyhedronfacetedge-disjoint pathssurvivable networkhop-constraint

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Paths and cycles (05C38)

Related Items (11)

Survivability in hierarchical telecommunications networks ⋮ The Minimum Spanning k-Core Problem with Bounded CVaR Under Probabilistic Edge Failures ⋮ Hop‐level flow formulation for the survivable network design with hop constraints problem ⋮ Robustness and Strong Attack Tolerance of Low-Diameter Networks ⋮ On the number of edges in a graph with many two-hop disjoint paths ⋮ A polyhedral study of the diameter constrained minimum spanning tree problem ⋮ The \(k\) edge-disjoint 3-hop-constrained paths polytope ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks ⋮ Characterization of facets of the hop constrained chain polytope via dynamic programming ⋮ Trade-offs among degree, diameter, and number of paths

Cites Work

• Unnamed Item
• On the directed hop-constrained shortest path problem
• Notes on polyhedra associated with hop-constrained paths
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• The 2-path network problem
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra

This page was built for publication: On the \(k\) edge-disjoint 2-hop-constrained paths polytope