Back to Search
Start Over
Approximation Algorithms for Connected Graph Factors of Minimum Weight.
- Source :
-
Theory of Computing Systems . Feb2018, Vol. 62 Issue 2, p441-464. 24p. - Publication Year :
- 2018
-
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). 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 A P X-hard. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 62
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 128169818
- Full Text :
- https://doi.org/10.1007/s00224-016-9723-z