Two Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedra
type: Dataset
description: Given a weighted undirected graph G with a set of pairs of terminals {si, ti}, i = 1, ..., d, and an integer L ≥ 2, the two node-disjoint hop-constrained survivable network design problem (TNHNDP) is to find a minimum weight subgraph of G such that between every si and ti there exist at least two node-disjoint paths of length at most L. This problem has applications to the design of survivable telecommunications networks with QoS-constraints. We discuss this problem from a polyhedral point of view. We present several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also discuss separation routines for these classes of inequalities. Using this, we propose a Branch-and-Cut algorithm for the problem when L = 3, and present some computational results.
issued: 2026-05-09T08:08:11.981233
language: en
modified: 2026-05-09T08:08:11.981238
contact point: Organization
  fn: CCSD
keyword: branch-and-cut
keyword: facet
keyword: hop-constraint
keyword: infoeu-reposemanticspreprint
keyword: infoinfo-cecomputer-science-cscomputational-engineering-finance-and-science-csce
keyword: infoinfo-rocomputer-science-csoperations-research-mathoc
keyword: node-disjoint-paths
keyword: polyhedron
keyword: preprints-working-papers-
keyword: survivable-network
landing page: https://hal.science/hal-00874354

Two Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedra
type: Distribution
format: HTML
issued: 2026-05-09T08:08:11.997806
modified: 2026-05-09T08:08:11.968480
access URL: https://hal.science/hal-00874354

test_moissonnage_selune
type: Agent