Please use this identifier to cite or link to this item:
Title: Resilient arcs and node disjointness in diverse routing
Authors: Gomes, Teresa 
Żotkiewicz, Mateusz 
Keywords: routing; protection; disjoint paths
Issue Date: 2014
Publisher: Elsevier
Citation: Teresa Gomes, Mateusz Żotkiewicz, Resilient arcs and node disjointness in diverse routing, Optical Switching and Networking, Volume 14, Part 2, 2014, Pages 149-163, ISSN 1573-4277, (
Project: PEst-OE/ EEI/UI308/2014 
ICIS Project CENTRO-07-0224-FEDER-002003 
National Science Center (Poland) under grant 2011/01/B/ST7/02967 
Serial title, monograph or event: Optical Switching and Networking
Volume: 14
Abstract: In multi-layer networks protection can be provided at multiple layers. Hence some links at an upper layer may be {\it resilient} because they are protected at a lower layer. We will designate as {\it resilient arc} at a given layer, an arc which has some form of protection at an underlaying layer. When path diversity is used at an upper layer, and resilient arcs are taken into account, it may not be necessary for the considered paths to be fully disjoint. We solve a problem of finding the shortest node-disjoint pair of paths that can share resilient arcs. It is assumed that a network consists of a set of nodes and a set of arcs. Moreover, a number of available arcs are resilient. Our goal is to find the shortest pair of paths such that they share only those nodes that are incident to shared resilient arcs. Moreover, we assume that the resulting paths cannot contain loops, and costs of shared resilient arcs are counted only once towards the objective function. In the paper we present two novel algorithms solving the above problem, and two supporting algorithms that are utilized as subroutines. We implement the proposed algorithms and compare them to an MIP approach.
DOI: 10.1016/j.osn.2014.05.022
Rights: openAccess
Appears in Collections:FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais
I&D INESCC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
GZ-OSN_2014-preprint_EstudoGeral.pdf393.59 kBAdobe PDFView/Open
Show full item record


checked on May 29, 2020

Citations 10

checked on Nov 2, 2021

Page view(s) 50

checked on Nov 25, 2021


checked on Nov 25, 2021

Google ScholarTM




This item is licensed under a Creative Commons License Creative Commons