Failure disjoint paths

Mateusz Zotkiewicz; W. Ben-Ameur; Michał Pióro

doi:10.1016/j.endm.2010.05.140

Failure disjoint paths

Mateusz Zotkiewicz, W. Ben-Ameur, Michał Pióro

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1105-1112
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	36
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2010.05.140
Publication status	Published - 1 Aug 2010
Externally published	Yes

Keywords

Disjoint paths
Polynomial time algorithms
Shortest paths

Access to Document

10.1016/j.endm.2010.05.140

Cite this

@article{9fcf7b26b551405e94d9b278ebdf4798,

title = "Failure disjoint paths",

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.",

keywords = "Disjoint paths, Polynomial time algorithms, Shortest paths",

author = "Mateusz Zotkiewicz and W. Ben-Ameur and Micha{\l} Pi{\'o}ro",

year = "2010",

month = aug,

day = "1",

doi = "10.1016/j.endm.2010.05.140",

language = "English",

volume = "36",

pages = "1105--1112",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

number = "C",

}

TY - JOUR

T1 - Failure disjoint paths

AU - Zotkiewicz, Mateusz

AU - Ben-Ameur, W.

AU - Pióro, Michał

PY - 2010/8/1

Y1 - 2010/8/1

N2 - 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.

AB - 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.

KW - Disjoint paths

KW - Polynomial time algorithms

KW - Shortest paths

U2 - 10.1016/j.endm.2010.05.140

DO - 10.1016/j.endm.2010.05.140

M3 - Article

AN - SCOPUS:77954942827

SN - 1571-0653

VL - 36

SP - 1105

EP - 1112

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

Failure disjoint paths

Abstract

Keywords

Access to Document

Fingerprint

Cite this