Title :
Maximum (s,t)-flows in planar networks in O(|V|log|V|) time
Author_Institution :
Fakultat fur Math., Konstanz Univ., Germany
Abstract :
Let G=(V, A) be a directed, planar graph, let s, t ∈ V, s≠t, and let ca>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 𝒪(|V|·3√|V|·log|V|) time, whereas the algorithm introduced in this paper requires only 𝒪(|V|log|V|) time
Keywords :
computational geometry; directed graphs; flow graphs; tree data structures; directed graphs; maximum (s,t)-flows; maximum flow; planar graph; planar networks; tree data structures; Algorithm design and analysis; Intelligent networks; Shortest path problem; Telecommunication traffic; Tree data structures; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365695
