10.4230/LIPICS.STACS.2009.1835
Borradaile, Glencora
Glencora
Borradaile
Demaine, Erik D.
Erik D.
Demaine
Tazari, Siamak
Siamak
Tazari
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Article
Polynomial-time approximation scheme
Bounded-genus graph
Embedded graph
Steiner tree
Survivable-network design
Subset TSP
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
2009
2009-02-19
2009-02-19
2009-02-19
en
urn:nbn:de:0030-drops-18355
10.4230/LIPIcs.STACS.2009
978-3-939897-09-5
1868-8969
10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS 2009
26th International Symposium on Theoretical Aspects of Computer Science
2013
3
13
171
182
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
3
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
239261 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 3, 26th International Symposium on Theoretical Aspects of Computer Science, pages 171-182