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

http://ir.library.oregonstate.edu/concern/articles/sb397b01k

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.

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
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
Series
Keyword
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2014-06-28T00:16:30Z (GMT) No. of bitstreams: 1 BorradaileGlencoraEECSPolynonialTimeApproximation.pdf: 465065 bytes, checksum: 125aea12cc2e64cdab76274a1b84333b (MD5)
  • description.provenance : Made available in DSpace on 2014-06-28T00:16:30Z (GMT). No. of bitstreams: 1 BorradaileGlencoraEECSPolynonialTimeApproximation.pdf: 465065 bytes, checksum: 125aea12cc2e64cdab76274a1b84333b (MD5) Previous issue date: 2014-02
  • description.provenance : Submitted by Deanne Bruner (deanne.bruner@oregonstate.edu) on 2014-06-28T00:15:59Z No. of bitstreams: 1 BorradaileGlencoraEECSPolynonialTimeApproximation.pdf: 465065 bytes, checksum: 125aea12cc2e64cdab76274a1b84333b (MD5)

Relationships

In Administrative Set:
Last modified: 07/26/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items