Finding disjoint paths in networks with star shared risk link groups

Jean-Claude Bermond 1 David Coudert 1 Gianlorenzo D 'Angelo 2 Fatima Zahra Moataz 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The notion of Shared Risk Link Groups (SRLG) has been introduced to capture surviv-ability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k-diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O(|V | 1−ε) for any 0 < ε < 1, where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 579, pp.74-87. 〈10.1016/j.tcs.2015.02.012〉
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01132216
Contributeur : David Coudert <>
Soumis le : lundi 16 mars 2015 - 18:47:42
Dernière modification le : lundi 4 décembre 2017 - 15:14:19
Document(s) archivé(s) le : lundi 17 avril 2017 - 15:59:01

Fichier

BCDM15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Claude Bermond, David Coudert, Gianlorenzo D 'Angelo, Fatima Zahra Moataz. Finding disjoint paths in networks with star shared risk link groups. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 579, pp.74-87. 〈10.1016/j.tcs.2015.02.012〉. 〈hal-01132216〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

237