Two Edge-Disjoint Hop-Constrained Paths and Polyhedra

DOI10.1137/S0895480102419445zbMath1077.90010OpenAlexW2065297120MaRDI QIDQ4652637

Pierre Pesneau, David Huygens, Ali Ridha Mahjoub

Publication date: 28 February 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480102419445

zbMATH Keywords

polyhedronfacetedge-disjoint pathshop-constraintssurvivable network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Survivability in hierarchical telecommunications networks ⋮ Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ 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 ⋮ On the \(k\) edge-disjoint 2-hop-constrained paths polytope ⋮ 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 ⋮ Distance Transformation for Network Design Problems ⋮ Hop-constrained node survivable network design: An application to MPLS over WDM ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ Trade-offs among degree, diameter, and number of paths

This page was built for publication: Two Edge-Disjoint Hop-Constrained Paths and Polyhedra