Abstract
Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2⋅⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k−1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2⋅⌈k/2⌉ (for k-edge-connectivity) or 2k−1 (for k-vertex-connectivity).
Original language | Undefined |
---|---|
Title of host publication | Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015) |
Editors | Laura Sanita, Martin Skutella |
Place of Publication | London |
Publisher | Springer |
Pages | 1-12 |
Number of pages | 12 |
ISBN (Print) | 978-3-319-28683-9 |
DOIs | |
Publication status | Published - 2016 |
Event | 13th Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece Duration: 17 Sep 2015 → 18 Sep 2015 Conference number: 13 http://algo2015.upatras.gr/waoa/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Verlag |
Volume | 9499 |
Conference
Conference | 13th Workshop on Approximation and Online Algorithms, WAOA 2015 |
---|---|
Abbreviated title | WAOA 2015 |
Country/Territory | Greece |
City | Patras |
Period | 17/09/15 → 18/09/15 |
Internet address |
Keywords
- METIS-316815
- IR-99710
- EWI-25741