Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

Authors Glencora Borradaile, Erik D. Demaine, Siamak Tazari



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1835.pdf
  • Filesize: 233 kB
  • 12 pages

Document Identifiers

Author Details

Glencora Borradaile
Erik D. Demaine
Siamak Tazari

Cite AsGet BibTex

Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 171-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1835

Abstract

We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in $O(n \log n)$ time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu (2007 and 2006) from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for planar graphs will similarly extend to bounded-genus graphs.
Keywords
  • Polynomial-time approximation scheme
  • Bounded-genus graph
  • Embedded graph
  • Steiner tree
  • Survivable-network design
  • Subset TSP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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