2026-07-23T05:04:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21145 2024-09-23T09:13:18Z ddc:004 open_access

Improved Approximations for Flexible Network Design Hyatt-Denesik, Dylan Jabal-Ameli, Afrouz Sanità, Laura Approximation Algorithms Network Design Flexible Connectivity Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed. In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dylan Hyatt-Denesik and Afrouz Jabal-Ameli and Laura Sanità 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.74 urn:nbn:de:0030-drops-211456 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.74 eng https://creativecommons.org/licenses/by/4.0/legalcode