Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults
International audience 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...
Published in: | Journal of Quaternary Science |
---|---|
Main Authors: | , , , |
Other Authors: | , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2022
|
Subjects: | |
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 |
Summary: | International audience 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. |
---|