Multiple-source multiple-sink maximum flow in planar graphs

Details Multiple-source multiple-sink maximum flow in planar graphs Multiple-source multiple-sink maximum flow in planar graphs

2010-12-21

arxiv.org/abs/1012.4767v2

Computer Science

Discrete Mathematics

Scientific paper

In this paper we show an O(n^(3/2) log^2 n) time algorithm for finding a maximum flow in a planar graph with multiple sources and multiple sinks. This is the fastest algorithm whose running time depends only on the number of vertices in the graph. For general (non-planar) graphs the multiple-source multiple-sink version of the maximum flow problem is as difficult as the standard single-source single-sink version. However, the standard reduction does not preserve the planarity of the graph, and it is not known how to generalize existing maximum flow algorithms for planar graphs to the multiple-source multiple-sink maximum flow problem.

Affiliated with

Also associated with

No associations

Rating

Multiple-source multiple-sink maximum flow in 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 Multiple-source multiple-sink maximum flow in planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple-source multiple-sink maximum flow in planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96754