Min st-cut oracle for planar graphs with near-linear preprocessing time

Glencora Borradaile; Piotr Sankowski; Christian Wulff-Nilsen

doi:10.1145/2684068

Min st-cut oracle for planar graphs with near-linear preprocessing time

Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen

Department of Computer Science

4 Citations (Scopus)

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 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.

Original language	English
Article number	16
Journal	A C M Transactions on Algorithms
Volume	11
Issue number	3
Pages (from-to)	16:1-16:29
ISSN	1549-6325
DOIs	https://doi.org/10.1145/2684068
Publication status	Published - 27 Oct 2014

Access to Document

10.1145/2684068

Cite this

@article{2a806341be67427ba8ede1cfeaee5bcf,

title = "Min st-cut oracle for planar graphs with near-linear preprocessing time",

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.",

keywords = "Minimum cut, minimum cycle basis, planar graphs",

author = "Glencora Borradaile and Piotr Sankowski and Christian Wulff-Nilsen",

year = "2014",

month = oct,

day = "27",

doi = "10.1145/2684068",

language = "English",

volume = "11",

pages = "16:1--16:29",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery, Inc.",

number = "3",

}

TY - JOUR

T1 - Min st-cut oracle for planar graphs with near-linear preprocessing time

AU - Borradaile, Glencora

AU - Sankowski, Piotr

AU - Wulff-Nilsen, Christian

PY - 2014/10/27

Y1 - 2014/10/27

N2 - 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.

AB - 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.

KW - Minimum cut, minimum cycle basis, planar graphs

U2 - 10.1145/2684068

DO - 10.1145/2684068

M3 - Journal article

SN - 1549-6325

VL - 11

SP - 16:1-16:29

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 16

ER -

Min st-cut oracle for planar graphs with near-linear preprocessing time

Abstract

Access to Document

Fingerprint

Cite this