Multiple source, single sink maximum flow in a planar graph

Abstract

We give an $O(n^{1.5}\log n)$ time algorithm for finding the maximum flow in a directed planar graph with multiple sources and a single sink. The techniques generalize to a subquadratic time algorithm for bounded genus graphs.

Cited by in corpus (1)

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