Maximum (s,t)-flows in planar networks in O(|V|log|V|) time
Karsten Weihe · 2002
Let G=(V, A) be a directed, planar graph, let s, t /spl isin/ V, s/spl ne/t, and let c/sub a/>0 be the capacity of an arc a/spl isin/A. The problem is to find a maximum flow from s to t in G: subject to these capacities. The fastest algorithm known so far requires /spl Oscr/(|V|/spl middot//sup 3//spl radic/|V|/spl middot/log|V|) time, whereas the algorithm introduced in this paper requires only /spl Oscr/(|V|log|V|) time.>