The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Failure disjoint paths

Author

  • M. Zotkiewicz
  • W. Ben-Ameur
  • Michal Pioro

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.

Publishing year

2010

Language

English

Pages

1105-1112

Publication/Series

Electronic Notes in Discrete Mathematics

Volume

36

Document type

Journal article

Publisher

Elsevier

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • shortest paths
  • disjoint paths
  • polynomial time algorithms

Conference name

International Symposium on Combinatorial Optimization

Conference date

2010-03-24 - 2010-03-26

Status

Published

Research group

  • Networking

ISBN/ISSN/Other

  • ISSN: 1571-0653