1 Search Results for "Zheng, Baigong"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.3
A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs

Authors: Glencora Borradaile and Baigong Zheng

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

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.
Cite as

Glencora Borradaile and Baigong Zheng. A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.APPROX-RANDOM.2017.3,
  author =	{Borradaile, Glencora and Zheng, Baigong},
  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 =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.3},
  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}
}
  • Refine by Author
  • 1 Borradaile, Glencora
  • 1 Zheng, Baigong

  • Refine by Classification

  • Refine by Keyword
  • 1 Planar Graphs
  • 1 Polynomial-Time Approximation Schemes
  • 1 Three-Edge Connectivity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact