Name
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 -regular spanning subgraphs (or -factors) of minimum weight with connectivity requirements. For the case of -edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all ≥2⋅⌈/2⌉. For the case of -vertex-connectedness, we achieve constant approximation ratios for ≥2−1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2⋅⌈/2⌉ (for -edge-connectivity) or 2−1 (for -vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is -hard. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s00224-016-9723-z | Theory Comput. Syst. |
Keywords | Field | DocType |
Graph factors,Edge-connectivity,Vertex-connectivity,Approximation algorithms | Discrete mathematics,Approximation algorithm,Combinatorics,Network planning and design,Travelling salesman problem,Vertex connectivity,Minimum weight,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
62 | 2 | 1432-4350 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kamiel Cornelissen | 1 | 4 | 2.08 |
| Ruben Hoeksma | 2 | 33 | 8.23 |
| Bodo Manthey | 3 | 147 | 13.30 |
| N. S. Narayanaswamy | 4 | 151 | 27.01 |
| C. S. Rahul | 5 | 2 | 2.43 |
| Marten Waanders | 6 | 0 | 0.34 |