OREGON STATE UNIVERSITY

You are here

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

TitleMultiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Publication TypeConference Paper
Year of Publication2011
AuthorsBorradaile, G., P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen
Conference Name2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
Pagination170 - 179
Date Published10.2011
PublisherIEEE
Conference LocationPalm Springs, CA
ISBN Number978-1-4577-1843-4
Abstract

We give an O(n log³ 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.

DOI10.1109/FOCS.2011.73