Computer Science – Data Structures and Algorithms
Scientific paper
2010-11-12
Computer Science
Data Structures and Algorithms
This paper is being merged with the paper by Christian Wulff-Nilsen "Min st-Cut of a Planar Graph in O(n loglog n) Time" htt
Scientific paper
In this paper we study minimum cut and maximum flow problems on planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph computes the minimum cut between any two given vertices in O(n log log n) time. Second, we show how to achieve the same O(n log log n) bound for the problem of computing maximum flows in undirected planar graphs. To the best of our knowledge, these are the first algorithms for those two problems that break the O(n log n) barrier, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm that is able to maintain information about minimum cuts and maximum flows in a plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert edges, delete edges and answer min-cut and max-flow queries between any pair of vertices in O(n^(2/3) log^3 n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial algorithm for min-cut and max-flow problems in a dynamic setting.
Italiano Giuseppe F.
Sankowski Piotr
No associations
LandOfFree
Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs 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 Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203560