The \(k\) edge-disjoint 3-hop-constrained paths polytope

DOI10.1016/j.disopt.2010.05.001zbMath1241.90155OpenAlexW1971023354MaRDI QIDQ429666

Ali Ridha Mahjoub, Jean Mailfert, Ibrahima Diarrassouba, Fatiha Bendali

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.05.001

zbMATH Keywords

polytopeflowfacetedge-disjoint pathshop-constrained pathssurvivable network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

Layered graph approaches for combinatorial optimization problems, 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, Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks, On the chance-constrained minimum spanning \(k\)-core problem, Distance Transformation for Network Design Problems, Trade-offs among degree, diameter, and number of paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on hop-constrained walk polytopes.
• Hop-constrained node survivable network design: An application to MPLS over WDM
• The 2-hop spanning tree problem
• The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points.
• On the directed hop-constrained shortest path problem
• Notes on polyhedra associated with hop-constrained paths
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On two-connected subgraph polytopes
• Steiner \(k\)-edge connected subgraph polyhedra
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• \(k\)-edge connected polyhedra on series-parallel graphs
• Critical extreme points of the 2-edge connected spanning subgraph polytope
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity 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
• The traveling salesman problem on a graph and some related integer polyhedra
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• The k-Edge-Connected Spanning Subgraph Polyhedron
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• The 2-path network problem
• Solving the Two-Connected Network with Bounded Meshes Problem
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• Design of Survivable Networks: A survey
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem