Multiple source, single sink maximum flow in a planar graph
Glencora BorradaileChristian Wulff-Nilsen
所有作者
Glencora BorradaileChristian Wulff-Nilsen
文献摘要
We give an O(n1.5logn) 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.