%0 Journal Article %1 borradaile2015stcut %A Borradaile, Glencora %A Sankowski, Piotr %A Wulff-Nilsen, Christian %C New York, NY, USA %D 2015 %I ACM %J ACM Trans. Algorithms %K cut oracle planar st %N 3 %P 16:1--16:29 %R 10.1145/2684068 %T Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time %U http://doi.acm.org/10.1145/2684068 %V 11 %X For an undirected n-vertex planar graph G with nonnegative 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 log4 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 log4 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 log2 n factor in the preprocessing times.

@article{borradaile2015stcut, abstract = {For an undirected n-vertex planar graph G with nonnegative 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 log4 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 log4 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 log2 n factor in the preprocessing times.}, acmid = {2684068}, added-at = {2015-01-16T11:08:14.000+0100}, address = {New York, NY, USA}, articleno = {16}, author = {Borradaile, Glencora and Sankowski, Piotr and Wulff-Nilsen, Christian}, biburl = {https://www.bibsonomy.org/bibtex/266e29caa1b488884b55894d11d2655a1/mtv_test}, description = {Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time}, doi = {10.1145/2684068}, interhash = {3906a74d83806c044e54927d2a51c36f}, intrahash = {66e29caa1b488884b55894d11d2655a1}, issn = {1549-6325}, issue_date = {January 2015}, journal = {ACM Trans. Algorithms}, keywords = {cut oracle planar st}, month = jan, number = 3, numpages = {29}, pages = {16:1--16:29}, publisher = {ACM}, timestamp = {2015-01-16T11:15:55.000+0100}, title = {Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time}, url = {http://doi.acm.org/10.1145/2684068}, volume = 11, year = 2015 }