Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus GraphsReportar como inadecuado




Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 University of Waterloo Waterloo 2 MIT - Massachusetts Institute of Technology 3 TU Darmstadt - Technische Universität Darmstadt

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 On log n time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu 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





Autor: Glencora Borradaile - Erik D. Demaine - Siamak Tazari -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados