Failure disjoint paths

Summary, in English

Given a weighted directed graph where some arcs can fail while others are reliable, we aim to compute a shortest pair of failure-disjoint paths. If a reliable arc is used by both paths, its cost is counted only once. We present a polynomial time algorithm to solve the problem.

• Författare: M. Zotkiewicz; W. Ben-Ameur; Michal Pioro
• Avdelning/ar: Institutionen för elektro- och informationsteknik; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publiceringsår: 2010
• Språk: Engelska
• Sidor: 1105-1112
• Publikation/Tidskrift/Serie: Electronic Notes in Discrete Mathematics
• Volym: 36
• Länkar: http://dx.doi.org/10.1016/j.endm.2010.05.140
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Electrical Engineering, Electronic Engineering, Information Engineering
• Nyckelord: shortest paths; disjoint paths; polynomial time algorithms
• Conference name: International Symposium on Combinatorial Optimization
• Conference date: 2010-03-24 - 2010-03-26
• Status: Published
• Forskningsgrupp: Networking
• ISBN/ISSN/Övrigt: ISSN: 1571-0653