Computer Science – Discrete Mathematics
Scientific paper
2011-05-11
Computer Science
Discrete Mathematics
18 pages, 1 figure
Scientific paper
We give an O(n log^3 n) algorithm that, given an n-node directed planar graph
with arc capacities, a set of source nodes, and a set of sink nodes, finds a
maximum flow from the sources to the sinks. Previously, the fastest algorithms
known for this problem were those for general graphs.
Borradaile Glencora
Klein Philip N.
Mozes Shay
Nussbaum Yahav
Wulff-Nilsen Christian
No associations
LandOfFree
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear 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 Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, 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 Directed Planar Graphs in Near-Linear Time will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-611850