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

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

2010-03-05

arxiv.org/abs/1003.1320v2

Computer Science

Discrete Mathematics

The previous version did not handle disconnected pieces or pieces with holes. This has been corrected in the new version at th

Scientific paper

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^5n)$ 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^5n)$ time and $O(n\log n)$ space and an explicit representation with additional $O(C)$ time and space where $C$ is the size of the basis. These results require that shortest paths be unique. We deterministically remove this assumption with an additional $\log^2 n$ factor in the running time.

Affiliated with

Also associated with

No associations

Rating

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688008