Article
 

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

Public Deposited

Contenu téléchargeable

Télécharger le fichier PDF
https://ir.library.oregonstate.edu/concern/articles/sb397b01k

Descriptions

Attribute NameValues
Creator
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 nonorientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu (2007) 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.
  • This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Springer and can be found at: http://link.springer.com/journal/453.
  • Keywords: Bounded-genus graphs, Steiner tree, Polynomial-time approximation scheme, Subset TSP
Resource Type
DOI
Date Available
Date Issued
Citation
  • Borradaile, G., Demaine, E. D., & Tazari, S. (2014). Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 68(2), 287-311. doi:10.1007/s00453-012-9662-2
Journal Title
Journal Volume
  • 68
Journal Issue/Number
  • 2
Déclaration de droits
Publisher
Peer Reviewed
Language
Replaces

Des relations

Parents:

This work has no parents.

Articles

La vignette Titre Date de téléchargement Visibilité actes
file details BorradaileGlencoraEECSPolynonialTimeApproximation.pdf 2017-07-26 Public Télécharger