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

Autor:	Adjiashvili, David, Hommelsheim, Felix, Mühlenthaler, Moritz, Schaudt, Oliver
Přispěvatelé:	Czumaj, Artur, Xin, Qin
Jazyk:	angličtina
Rok vydání:	2022
Předmět:	graph algorithms Mathematics of computing → Approximation algorithms network design Theory of computation → Routing and network design problems fault tolerance approximation algorithms Theory of computation → Network flows MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Leibniz International Proceedings in Informatics (LIPIcs), 227
ISSN:	1868-8969
Popis:	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. Leibniz International Proceedings in Informatics (LIPIcs), 227 ISSN:1868-8969
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3537561a0c7e9717067933f94e555aa8 https://hdl.handle.net/20.500.11850/557702 Zobrazit plný text záznamu