Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs |
| |
Authors: | Glencora Borradaile Erik D. Demaine Siamak Tazari |
| |
Affiliation: | 1. Oregon State University, 1148 Kelley Engineering Center, Corvallis, OR, 97331, USA 2. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 32 Vassar Streeet, Cambridge, MA, 02139, USA
|
| |
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 $mathcal{O}(n log n)$ time for graphs embedded on both orientable and nonorientable surfaces. This work generalizes the PTAS framework from planar graphs to bounded-genus graphs: any problem that is shown to be approximable by the planar PTAS framework of Borradaile et al. (ACM Trans. Algorithms 5(3), 2009) will also be approximable in bounded-genus graphs by our extension. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|