OREGON STATE UNIVERSITY

You are here

Boundary-to-boundary flows in planar graphs

TitleBoundary-to-boundary flows in planar graphs
Publication TypeJournal Article
Year of Publication2013
AuthorsBorradaile, G., and A. Harutyunyan
JournalCoRR
Volumeabs/1306.5391
Date Published05/2013
Abstract

We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only O(n) queries to simple data structures, achieving an O(n log n) running time that we expect to be practical given the use of simple primitives. The only existing algorithm for this problem uses divide and conquer and, in order to achieve an O(n log n) running time, requires the use of the (complicated) linear-time shortest-paths algorithm for planar graphs.