Skip to Main content Skip to Navigation
Reports

Diverse Routing with the star property

Jean-Claude Bermond 1 David Coudert 1 Gianlorenzo d'Angelo 1 Fatima Zahra Moataz 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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 survivability issues where a set of links of a network fail simultaneously. In this context, the \emph{diverse routing} problem is to find a set of SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proved $NP$-complete in general~\cite{Hu03} and some polynomial instances have been characterized~\cite{CDP+07}. In this paper, we investigate the diverse routing problem in networks satisfying the \emph{star property}~\cite{LW05}. This property states that an edge may be subject to several SRLGs but all edges subject to a given SRLG are incident to a common node. We first provide counter-examples to the polynomial time algorithm proposed in~\cite{LW05} for computing pairs of SRLG-disjoint paths in networks with the star property, and then prove that this problem is in fact $NP$-hard in the strong sense. More generally, we prove that the diverse routing problem in networks with the star property is $NP$-hard in the strong sense, hard to approximate, and $W[1]$-hard when the parameter is the number of SRLG-disjoint paths. Last, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLG is constant, the maximum degree of the vertices is strictly smaller than 5, and when the network is a directed acyclic graph.
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-00733869
Contributor : Gianlorenzo d'Angelo <>
Submitted on : Wednesday, September 19, 2012 - 6:57:08 PM
Last modification on : Tuesday, November 17, 2020 - 11:18:04 PM
Long-term archiving on: : Friday, December 16, 2016 - 3:36:42 PM

File

RR-8071.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00733869, version 1

Collections

Citation

Jean-Claude Bermond, David Coudert, Gianlorenzo d'Angelo, Fatima Zahra Moataz. Diverse Routing with the star property. [Research Report] RR-8071, INRIA. 2012. ⟨hal-00733869⟩

Share

Metrics

Record views

438

Files downloads

286