Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set o...

Full description

Bibliographic Details
Published in:Journal of Quaternary Science
Main Authors: Adjiashvili, David, Hommelsheim, Felix, Mühlenthaler, Moritz, Schaudt, Oliver
Other Authors: Department of Mathematics - ETH, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology Zürich (ETH Zürich), Faculty of Computer Science and Mathematics Bremen, University of Bremen, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut fur Mathematik, RWTH Aachen Univers
Format: Conference Object
Language:English
Published: HAL CCSD 2022
Subjects:
network design
fault tolerance
approximation algorithms
graph algorithms
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Faroe Islands
Torshavn
Online Access:https://hal.science/hal-04214508
https://hal.science/hal-04214508/document
https://hal.science/hal-04214508/file/LIPIcs-SWAT-2022-5.pdf
https://doi.org/10.4230/LIPIcs.SWAT.2022.5
Description
Summary:The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.

Similar Items