Technical Report 390-1994

Title

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

Author

Karsten Weihe

Publication

Proc. 35th Annual Symp. Foundations of Computer Science (FOCS '94), 1994, pp. 178-189

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

Let G=(V,A) be a directed, planar graph, let `s,t&; V,s eq t, and let c_a>0` be the capacity of an arc a&; 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 O(|V|cdotsqrt[3]{|V|}cdotlog|V|) time, whereas the algorithm introduced in this paper requires only O(|V|log|V|) time.