OREGON STATE UNIVERSITY

You are here

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

TitlePolynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Publication TypeConference Paper
Year of Publication2009
AuthorsBorradaile, G., E. D. Demaine, and S. Tazari
Conference Name26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Pagination171–182
Date Published02/2009
PublisherSchloss Dagstuhl–Leibniz-Zentrum fuer Informatik
Conference LocationDagstuhl, Germany
ISBN Number978-3-939897-09-05
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.

URLhttp://drops.dagstuhl.de/opus/volltexte/2009/1835
DOI10.4230/LIPIcs.STACS.2009.1835