Title :
Partition of planar flow networks
Author :
Johnson, Donald B. ; Venkatesan, Shankar M.
Abstract :
We give a new characterization of the planar separator theorem in terms of mutually non-containing closed Jordan Curves. using this, we develop an O(n √n logn) maximum flow algorithm for directed planar networks (hence for any planar network).
Keywords :
Computer science; Particle separators; Partitioning algorithms; Tree graphs;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.44