Two node-disjoint 3-hop-constrained survivable network design and polyhedra
Küçük Resim Yok
Tarih
2013
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
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. © 2013 Elsevier B.V.
Açıklama
Anahtar Kelimeler
Branch-and-cut, Facet, Hop constraint, Node-disjoint paths, Polyhedron, Survivable network
Kaynak
Electronic Notes in Discrete Mathematics
WoS Q Değeri
Scopus Q Değeri
Q4
Cilt
41
