Approximation Algorithms for k-Connected Graph Factors

Bodo Manthey; Marten Waanders

doi:10.1007/978-3-319-28684-6_1

Approximation Algorithms for k-Connected Graph Factors

Bodo Manthey, Marten Waanders

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

10 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).

Original language	Undefined
Title of host publication	Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015)
Editors	Laura Sanita, Martin Skutella
Place of Publication	London
Publisher	Springer
Pages	1-12
Number of pages	12
ISBN (Print)	978-3-319-28683-9
DOIs	https://doi.org/10.1007/978-3-319-28684-6_1
Publication status	Published - 2016
Event	13th Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece Duration: 17 Sept 2015 → 18 Sept 2015 Conference number: 13 http://algo2015.upatras.gr/waoa/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9499

Conference

Conference	13th Workshop on Approximation and Online Algorithms, WAOA 2015
Abbreviated title	WAOA 2015
Country/Territory	Greece
City	Patras
Period	17/09/15 → 18/09/15
Internet address	http://algo2015.upatras.gr/waoa/

Keywords

METIS-316815
IR-99710
EWI-25741

Access to Document

10.1007/978-3-319-28684-6_1

http://eprints.eemcs.utwente.nl/secure2/25741/01/WAOA2015_MantheyWaanders_ConnectedFactors.pdf

Cite this

@inproceedings{3cfe2b95c5dc4e078449e176da96d2df,

title = "Approximation Algorithms for k-Connected Graph Factors",

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).",

keywords = "METIS-316815, IR-99710, EWI-25741",

author = "Bodo Manthey and Marten Waanders",

note = "eemcs-eprint-25741 ; 13th Workshop on Approximation and Online Algorithms, WAOA 2015 ; Conference date: 17-09-2015 Through 18-09-2015",

year = "2016",

doi = "10.1007/978-3-319-28684-6\_1",

language = "Undefined",

isbn = "978-3-319-28683-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--12",

editor = "Laura Sanita and Martin Skutella",

booktitle = "Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015)",

address = "Germany",

url = "http://algo2015.upatras.gr/waoa/",

}

Manthey, B & Waanders, M 2016, Approximation Algorithms for k-Connected Graph Factors. in L Sanita & M Skutella (eds), Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015). Lecture Notes in Computer Science, vol. 9499, Springer, London, pp. 1-12, 13th Workshop on Approximation and Online Algorithms, WAOA 2015, Patras, Greece, 17/09/15. https://doi.org/10.1007/978-3-319-28684-6_1

Approximation Algorithms for k-Connected Graph Factors. / Manthey, Bodo; Waanders, Marten.
Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015). ed. / Laura Sanita; Martin Skutella. London: Springer, 2016. p. 1-12 (Lecture Notes in Computer Science; Vol. 9499).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation Algorithms for k-Connected Graph Factors

AU - Manthey, Bodo

AU - Waanders, Marten

N1 - Conference code: 13

PY - 2016

Y1 - 2016

N2 - 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).

AB - 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).

KW - METIS-316815

KW - IR-99710

KW - EWI-25741

U2 - 10.1007/978-3-319-28684-6_1

DO - 10.1007/978-3-319-28684-6_1

M3 - Conference contribution

SN - 978-3-319-28683-9

T3 - Lecture Notes in Computer Science

SP - 1

EP - 12

BT - Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015)

A2 - Sanita, Laura

A2 - Skutella, Martin

PB - Springer

CY - London

T2 - 13th Workshop on Approximation and Online Algorithms, WAOA 2015

Y2 - 17 September 2015 through 18 September 2015

ER -