Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.08972 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914753739227136 |
|---|---|
| author | Hyatt-Denesik, Dylan Ameli, Afrouz Jabal Sanita, Laura |
| author_facet | Hyatt-Denesik, Dylan Ameli, Afrouz Jabal Sanita, Laura |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_08972 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Approximations for Flexible Network Design Hyatt-Denesik, Dylan Ameli, Afrouz Jabal Sanita, Laura Data Structures and Algorithms 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. |
| title | Improved Approximations for Flexible Network Design |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.08972 |