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

CNRS UMR 5157 SAMOVAR
Institute of Telecommunications
Warsaw University of Technology
Department of Electrical and Information Technology
Lund University

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

1 Citation (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	1105-1112
Nombre de pages	8
journal	Electronic Notes in Discrete Mathematics
Volume	36
Numéro de publication	C
Les DOIs	https://doi.org/10.1016/j.endm.2010.05.140
état	Publié - 1 août 2010
Modification externe	Oui

Accès au document

10.1016/j.endm.2010.05.140

Contient cette citation

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

publisher = "Elsevier B.V.",

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation