Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time

摘要

LetG=(V, A) be a directed, planar graph, lets, t∈V,s≠t, and letca>0 be the capacity of an arca∈A. The problem is to find a maximum flow fromstotinGsubject to these capacities. The best asymptotic bound known so far is O(n log n·min{n,n log C{), wheren=|V| andC=∑a∈A ca. We introduce a new algorithm, which requires only O(n log n) time.