Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; and
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
conference dates
2010-03-24 - 2010-03-26
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
2016-04-04 09:34:24
date last changed
2022-01-29 18:32:32
@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}},
  keywords     = {{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}},
  doi          = {{10.1016/j.endm.2010.05.140}},
  volume       = {{36}},
  year         = {{2010}},
}