Advanced

Failure disjoint paths

Zotkiewicz, M.; Ben-Ameur, W. and Pioro, Michal LU (2010) International Symposium on Combinatorial Optimization In Electronic Notes in Discrete Mathematics 36. p.1105-1112
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
shortest paths, disjoint paths, polynomial time algorithms
in
Electronic Notes in Discrete Mathematics
volume
36
pages
1105 - 1112
publisher
Elsevier
conference name
International Symposium on Combinatorial Optimization
external identifiers
  • scopus:77954942827
ISSN
1571-0653
DOI
10.1016/j.endm.2010.05.140
language
English
LU publication?
yes
id
dddfc761-9ca7-4ab4-861f-3ffe07f678cd (old id 1719982)
date added to LUP
2010-11-22 10:40:26
date last changed
2017-01-01 07:51:24
@article{dddfc761-9ca7-4ab4-861f-3ffe07f678cd,
  abstract     = {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.},
  author       = {Zotkiewicz, M. and Ben-Ameur, W. and Pioro, Michal},
  issn         = {1571-0653},
  keyword      = {shortest paths,disjoint paths,polynomial time algorithms},
  language     = {eng},
  pages        = {1105--1112},
  publisher    = {Elsevier},
  series       = {Electronic Notes in Discrete Mathematics},
  title        = {Failure disjoint paths},
  url          = {http://dx.doi.org/10.1016/j.endm.2010.05.140},
  volume       = {36},
  year         = {2010},
}