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 |
id |
ftunigrenoble:oai:HAL:hal-04214508v1 |
---|---|
record_format |
openpolar |
spelling |
ftunigrenoble:oai:HAL:hal-04214508v1 2024-05-12T08:03:26+00:00 Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver 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 Torshavn, Faroe Islands 2022-06-27 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 en eng HAL CCSD Schloss Dagstuhl - Leibniz-Zentrum für Informatik info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SWAT.2022.5 hal-04214508 https://hal.science/hal-04214508 https://hal.science/hal-04214508/document https://hal.science/hal-04214508/file/LIPIcs-SWAT-2022-5.pdf doi:10.4230/LIPIcs.SWAT.2022.5 info:eu-repo/semantics/OpenAccess 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT https://hal.science/hal-04214508 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, Jun 2022, Torshavn, Faroe Islands. pp.5:1--5:19, ⟨10.4230/LIPIcs.SWAT.2022.5⟩ network design fault tolerance approximation algorithms graph algorithms [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] info:eu-repo/semantics/conferenceObject Conference papers 2022 ftunigrenoble https://doi.org/10.4230/LIPIcs.SWAT.2022.5 2024-04-18T02:48:50Z 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. Conference Object Faroe Islands Torshavn Université Grenoble Alpes: HAL Faroe Islands Journal of Quaternary Science 35 6 803 816 |
institution |
Open Polar |
collection |
Université Grenoble Alpes: HAL |
op_collection_id |
ftunigrenoble |
language |
English |
topic |
network design fault tolerance approximation algorithms graph algorithms [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
spellingShingle |
network design fault tolerance approximation algorithms graph algorithms [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
topic_facet |
network design fault tolerance approximation algorithms graph algorithms [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
description |
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. |
author2 |
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 |
author |
Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver |
author_facet |
Adjiashvili, David Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver |
author_sort |
Adjiashvili, David |
title |
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
title_short |
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
title_full |
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
title_fullStr |
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
title_full_unstemmed |
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults |
title_sort |
fault-tolerant edge-disjoint s-t paths - beyond uniform faults |
publisher |
HAL CCSD |
publishDate |
2022 |
url |
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 |
op_coverage |
Torshavn, Faroe Islands |
geographic |
Faroe Islands |
geographic_facet |
Faroe Islands |
genre |
Faroe Islands Torshavn |
genre_facet |
Faroe Islands Torshavn |
op_source |
18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT https://hal.science/hal-04214508 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, Jun 2022, Torshavn, Faroe Islands. pp.5:1--5:19, ⟨10.4230/LIPIcs.SWAT.2022.5⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SWAT.2022.5 hal-04214508 https://hal.science/hal-04214508 https://hal.science/hal-04214508/document https://hal.science/hal-04214508/file/LIPIcs-SWAT-2022-5.pdf doi:10.4230/LIPIcs.SWAT.2022.5 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.4230/LIPIcs.SWAT.2022.5 |
container_title |
Journal of Quaternary Science |
container_volume |
35 |
container_issue |
6 |
container_start_page |
803 |
op_container_end_page |
816 |
_version_ |
1798845550616903680 |