Show simple item record

hal.structure.identifier
dc.contributor.authorMahjoub, Ali Ridha*
hal.structure.identifier
dc.contributor.authorKutucu, Hakan*
hal.structure.identifier
dc.contributor.authorDiarrassouba, Ibrahima
HAL ID: 745402
*
dc.date.accessioned2013-11-19T13:49:35Z
dc.date.available2013-11-19T13:49:35Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12102
dc.language.isoenen
dc.subjectbranch and cuten
dc.subjecthop constrainten
dc.subjectnode-disjoint pathsen
dc.subjectSurvivable networken
dc.subject.ddc511en
dc.titleTwo Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedraen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Mathematics, Izmir Institute of Technology, Izmir;Turquie
dc.contributor.editoruniversityotherDépartement de Mathématiques, Université du Havre.;France
dc.description.abstractenGiven 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.en
dc.relation.isversionofjnlnameElectronic Notes in Discrete Mathematics
dc.relation.isversionofjnlvol41
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages551-558
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.endm.2013.05.137
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00874354en
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record