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 等数据库收录！ |
|
