Approximation Algorithms for Connected Graph Factors of Minimum Weight

作者：Cornelissen Kamiel; Hoeksma Ruben; Manthey Bodo; Narayanaswamy N S; Rahul C S; Waanders Marten

来源：Theory of Computing Systems, 2018, 62(2): 441-464.

DOI：10.1007/s00224-016-9723-z

• Graph factors
• Edge-connectivity
• Vertex-connectivity
• Approximation algorithms

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 . For the case of k-vertex-connectedness, we achieve constant approximation ratios for dae -1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least (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 APX-hard.

• 出版日期2018-2