Approximation Algorithms for Connected Graph Factors of Minimum Weight

Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey* (Corresponding Author), N.S. Narayanaswamy, C.S. Rahul, Marten Waanders

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
40 Downloads (Pure)

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 APX-hard.

Original languageEnglish
Pages (from-to)441-464
Number of pages24
JournalTheory of computing systems
Volume62
Issue number2
DOIs
Publication statusPublished - 1 Feb 2018

Keywords

  • UT-Hybrid-D
  • Edge-connectivity
  • Graph factors
  • Vertex-connectivity
  • Approximation algorithms

Fingerprint Dive into the research topics of 'Approximation Algorithms for Connected Graph Factors of Minimum Weight'. Together they form a unique fingerprint.

  • Cite this

    Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N. S., Rahul, C. S., & Waanders, M. (2018). Approximation Algorithms for Connected Graph Factors of Minimum Weight. Theory of computing systems, 62(2), 441-464. https://doi.org/10.1007/s00224-016-9723-z