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

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)))\).


90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
Full Text: EuDML Link


[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.