Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time Public Deposited

http://ir.library.oregonstate.edu/concern/articles/5m60qt57r

© ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Algorithms (TALG), 11(3), Article 16, (January 2015)}  http://doi.acm.org/10.1145/2684068

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log⁴ n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log⁴ n) time and O(n log n) space. Additionally, an explicit representation can be obtained in O(C) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead, or deterministically with an additional log² n factor in the preprocessing times.
Resource Type
DOI
Date Available
Date Issued
Citation
  • Borradaile, G., Sankowski, P., & Wulff-Nilsen, C. (2015). Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. ACM Transactions on Algorithms (TALG), 11(3), 16. doi:10.1145/2684068
Series
Keyword
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2015-07-10T22:35:20Z (GMT). No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerScienceMinSt-CutOraclePlanarGraphs.pdf: 1869613 bytes, checksum: 5dc3aa6e3d1bd5b3b064973c5eaba8b4 (MD5) Previous issue date: 2015-01
  • description.provenance : Submitted by Deanne Bruner (deanne.bruner@oregonstate.edu) on 2015-07-10T22:33:01Z No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerScienceMinSt-CutOraclePlanarGraphs.pdf: 1869613 bytes, checksum: 5dc3aa6e3d1bd5b3b064973c5eaba8b4 (MD5)
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2015-07-10T22:35:20Z (GMT) No. of bitstreams: 1 BorradaileGlencoraElectricalEngeeringComputerScienceMinSt-CutOraclePlanarGraphs.pdf: 1869613 bytes, checksum: 5dc3aa6e3d1bd5b3b064973c5eaba8b4 (MD5)

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items