License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.3
URN: urn:nbn:de:0030-drops-75525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7552/
Go to the corresponding LIPIcs Volume Portal

Borradaile, Glencora ; Zheng, Baigong

A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs

pdf-format:
LIPIcs-APPROX-RANDOM-2017-3.pdf (0.6 MB)

Abstract

We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement r in {0, 1, 2, 3} for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices u and v, at least min{r(v), r(u)} edge-disjoint u-to-v paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge (paying for each edge separately). This generalizes an earlier result for r in {0, 1, 2}. In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.

BibTeX - Entry

@InProceedings{borradaile_et_al:LIPIcs:2017:7552,
  author =	{Glencora Borradaile and Baigong Zheng},
  title =	{{A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7552},
  URN =		{urn:nbn:de:0030-drops-75525},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.3},
  annote =	{Keywords: Three-Edge Connectivity, Polynomial-Time Approximation Schemes, Planar Graphs}
}

Keywords: Three-Edge Connectivity, Polynomial-Time Approximation Schemes, Planar Graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI