Minimum cut in directed planar networks. (English) Zbl 0763.90084

Janiga, Ladislav; Koubek, Václav

Kybernetika 28, No. 1, 37-49 (1992).

Summary: An algorithm which for any planar directed network with \(n\) nodes finds its minimum cut in time \(O(n \log^ 2(n)/\log(\log(n)))\) is presented. For the case \(s-t\)-network this time is reduced by the factor of \(\log(n)\), i.e. to \(O(n \log(n)/\log(\log(n)))\).

MSC:

90C35	Programming involving graphs or networks
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

planar directed network; minimum cut

References:

[1]	A.V. Aho J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. 1974. · Zbl 0326.68005
[2]	E. W. Dijkstra: A note on two problems in connections with graphs. Numer. Math. 1 (1959), 269 - 271. · Zbl 0092.16002
[3]	P. van Emde Boas R. Kaas, E. Zijlstra: Design and implementation of an efficient priority queue. Math. Systems Theory 10 (1977), 99 - 127. · Zbl 0363.60104
[4]	L. R. Ford, D.R. Fulkerson: Flows in Networks. Princeton University Press, Princeton, N.J. 1962. · Zbl 0106.34802
[5]	L. M. Fredman, R. E. Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach. 34 (1987), 596 - 615.
[6]	L. M. Fredman, D. E. Willard: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Proc. 31st FOCS, 1990, pp. 719 - 725. · Zbl 0806.68057
[7]	R. Hassin, D.B. Johnson: An \(O (n \log^{2}(n))\) algorithm for maximum flow in undirected planar network. SIAM J. Comput. 14 (1985), 612 - 624. · Zbl 0565.90018
[8]	J. E. Hopcroft, R. E. Tarjan: Efficient planarity testing. J. Assoc. Comput. Mach. 21 (1974), 549 - 568. · Zbl 0307.68025
[9]	A. Itai, Y. Shiloach: Maximum flow in planar networks. SIAM J. Comput. 8 (1979), 135 - 150. · Zbl 0419.90040
[10]	L. Janiga, V. Koubek: A note on finding minimum cuts in directed planar network by parallel computations. Inform. Process. Lett. 21 (1985), 75 - 78. · Zbl 0583.90026
[11]	D.B. Johnson, S. Venkatesan: Using divide and conquer to find flows in directed planar networks in \(O(n^{15}\log(n))\) time. Proc. 20th Annual Allerton Conf. of Communication, Control and Computing, 1982, pp. 898 - 905.
[12]	K. Mehlhorn: Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - Tokio 1984. · Zbl 0556.68002
[13]	O. Ore: Theory of Graphs. Amer. Math. Soc. Coll. Publ., Vol. XXXVIII, Providence, R.I. 1962. · Zbl 0105.35401
[14]	J. H. Reif: Minimum S-T cut of a planar undirected network on \(O(n \log^{2} (n))\) time. Automata, Languages and Programming (S. Even, D. Kariv, Lecture Notes in Computer Science 115), Springer-Verlag, Berlin - Heidelberg - New York - Tokio 1981, pp. 56 - 67.