Premium
Two node‐disjoint hop‐constrained survivable network design and polyhedra
Author(s) -
Diarrassouba Ibrahima,
Kutucu Hakan,
Mahjoub A. Ridha
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21679
Subject(s) - polyhedron , disjoint sets , computer science , node (physics) , hop (telecommunications) , graph , dominating set , integer programming , network planning and design , set (abstract data type) , integer (computer science) , combinatorics , mathematics , discrete mathematics , mathematical optimization , computer network , theoretical computer science , algorithm , structural engineering , engineering , programming language , vertex (graph theory)
Given a weighted undirected graph G with a set of pairs of terminals ( s i , t i ), i = 1 , … , d , and an integer L ≥ 2 , the two node‐disjoint hop‐constrained survivable network design problem is to find a minimum weight subgraph of G such that between every s i and t i there exist at least two node‐disjoint paths of length at most L . This problem has applications in the design of survivable telecommunication 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, and propose a Branch‐and‐Cut algorithm for the problem when L = 3, as well as some computational results. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 316–337 2016