Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. Borradaile, G., Sankowski, P., & Wulff-Nilsen, C. ACM Trans. Algorithms, 11(3):16:1--16:29, ACM, New York, NY, USA, January, 2015. ![Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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 = {http://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 = {January},
number = {3},
numpages = {29},
pages = {16:1--16:29},
publisher = {ACM},
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}
}
Downloads: 0
{"_id":"MEKhuqCmAnGwNBQim","authorIDs":[],"author_short":["Borradaile, G.","Sankowski, P.","Wulff-Nilsen, C."],"bibbaseid":"borradaile-sankowski-wulffnilsen-minstcutoracleforplanargraphswithnearlinearpreprocessingtime-2015","bibdata":{"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","Sankowski, Piotr","Wulff-Nilsen, Christian"],"author_short":["Borradaile, G.","Sankowski, P.","Wulff-Nilsen, C."],"bibtex":"@article{ borradaile2015stcut,\n 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.},\n acmid = {2684068},\n added-at = {2015-01-16T11:08:14.000+0100},\n address = {New York, NY, USA},\n articleno = {16},\n author = {Borradaile, Glencora and Sankowski, Piotr and Wulff-Nilsen, Christian},\n biburl = {http://www.bibsonomy.org/bibtex/266e29caa1b488884b55894d11d2655a1/mtv_test},\n description = {Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time},\n doi = {10.1145/2684068},\n interhash = {3906a74d83806c044e54927d2a51c36f},\n intrahash = {66e29caa1b488884b55894d11d2655a1},\n issn = {1549-6325},\n issue_date = {January 2015},\n journal = {ACM Trans. Algorithms},\n keywords = {cut oracle planar st},\n month = {January},\n number = {3},\n numpages = {29},\n pages = {16:1--16:29},\n publisher = {ACM},\n title = {Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time},\n url = {http://doi.acm.org/10.1145/2684068},\n volume = {11},\n year = {2015}\n}","bibtype":"article","biburl":"http://www.bibsonomy.org/bibtex/266e29caa1b488884b55894d11d2655a1/mtv_test","description":"Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time","doi":"10.1145/2684068","id":"borradaile2015stcut","interhash":"3906a74d83806c044e54927d2a51c36f","intrahash":"66e29caa1b488884b55894d11d2655a1","issn":"1549-6325","issue_date":"January 2015","journal":"ACM Trans. Algorithms","key":"borradaile2015stcut","keywords":"cut oracle planar st","month":"January","number":"3","numpages":"29","pages":"16:1--16:29","publisher":"ACM","title":"Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time","type":"article","url":"http://doi.acm.org/10.1145/2684068","volume":"11","year":"2015","bibbaseid":"borradaile-sankowski-wulffnilsen-minstcutoracleforplanargraphswithnearlinearpreprocessingtime-2015","role":"author","urls":{"Paper":"http://doi.acm.org/10.1145/2684068"},"keyword":["cut oracle planar st"],"downloads":0},"bibtype":"article","biburl":"http://www.bibsonomy.org/bib/author/Piotr Sankowski?items=1000","creationDate":"2015-01-18T04:58:36.646Z","downloads":0,"keywords":["st planar oracle cut","cut oracle planar st"],"search_terms":["min","cut","oracle","planar","graphs","near","linear","preprocessing","time","borradaile","sankowski","wulff-nilsen"],"title":"Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time","year":2015,"dataSources":["FETg9T89pvSag5tt5"]}