Two Edge-Disjoint Hop-Constrained Paths and Polyhedra

DOI10.1137/S0895480102419445MaRDI QIDQ4652637zbMATH OpenOpenAlexFDO

Authors David Huygens, Pierre Pesneau, A. R. 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

edge-disjoint pathspolyhedronfacethop-constraintssurvivable network

Mathematics Subject Classification ID

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

Recommendations

• The k edge-disjoint 3-hop-constrained paths polytope
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Integer programming formulations for the two 4-hop-constrained paths problem
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Two node-disjoint hop-constrained survivable network design and polyhedra

Cited in

(24)

• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Integer programming formulations for the two 4-hop-constrained paths problem
• Characterization of facets of the hop constrained chain polytope via dynamic programming
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Trade-offs among degree, diameter, and number of paths
• CONSTRAINED DISJOINT PATHS IN GEOMETRIC NETWORKS
• The minimum spanning k-core problem with bounded CVaR under probabilistic edge failures
• The k edge-disjoint 3-hop-constrained paths polytope
• Survivability in hierarchical telecommunications networks
• Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
• Composition of graphs and the hop-constrained path problem
• On the number of edges in a graph with many two-hop disjoint paths
• Distance transformation for network design problems
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• Robustness and strong attack tolerance of low-diameter networks
• Hop-level flow formulation for the survivable network design with hop constraints problem
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Hop-constrained node survivable network design: An application to MPLS over WDM
• Critical extreme points of the 2-edge connected spanning subgraph polytope
• Two node-disjoint hop-constrained survivable network design and polyhedra
• 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: Two Edge-Disjoint Hop-Constrained Paths and Polyhedra

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