Finding The Shortest Node-Disjoint Pair of Paths That Are Allowed To Share Resilient Arcs

Teresa Gomez , Mateusz Żotkiewicz


We have solved 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. Furthermore, we assume that the resulting paths cannot contain loops. In the paper we present two novel algorithms solving the above problem. We implement the proposed algorithms and compare them to an MIP approach.
Author Teresa Gomez
Teresa Gomez,,
, Mateusz Żotkiewicz (FEIT / IT)
Mateusz Żotkiewicz,,
- The Institute of Telecommunications
Pages179 - 186
Book Rak Jacek, Mouftah Hussein, Zhong Wen-De (eds.): Proceedings of the RNDM 2013 5th International Workshop on Reliable Networks Design and Modeling, 2013, Almaty, IEEE Communications Society, ISBN 978-1-4799-1376-3, 300 p.
RNDM13_final_program.pdf / 3.19 MB / No licence information
Keywords in Englishrouting, protection, disjoint paths
ProjectMixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
Gomez Zotkiewicz Finding the shortest node-disjoint 2013.pdf 440.55 KB
Score (nominal)0
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?