Approximation Algorithms for k-Connected Graph Factors

Bodo Manthey, Marten Waanders

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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 languageUndefined
Title of host publicationProceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015)
EditorsLaura Sanita, Martin Skutella
Place of PublicationLondon
PublisherSpringer
Pages1-12
Number of pages12
ISBN (Print)978-3-319-28683-9
DOIs
Publication statusPublished - 2016
Event13th Workshop on Approximation and Online Algorithms 2015 - Patras, Greece
Duration: 17 Sep 201518 Sep 2015
Conference number: 13
http://algo2015.upatras.gr/waoa/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9499

Conference

Conference13th Workshop on Approximation and Online Algorithms 2015
Abbreviated titleWAOA 2015
CountryGreece
CityPatras
Period17/09/1518/09/15
Internet address

Keywords

  • METIS-316815
  • IR-99710
  • EWI-25741

Cite this