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 pathsfacethop-constraintspolyhedronsurvivable network

Mathematics Subject Classification ID

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

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

(25)

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

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)