Geodesic
Minimum cut in directed planar networks
Kybernetika, Tome 28 (1992) no. 1, pp. 37-49 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C85, 90B10, 90C35, 90C60 
@article{KYB_1992_28_1_a2,
     author = {Janiga, Ladislav and Koubek, V\'aclav},
     title = {Minimum cut in directed planar networks},
     journal = {Kybernetika},
     pages = {37--49},
     year = {1992},
     volume = {28},
     number = {1},
     mrnumber = {1159873},
     zbl = {0763.90084},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_1992_28_1_a2/}
}
TY  - JOUR
AU  - Janiga, Ladislav
AU  - Koubek, Václav
TI  - Minimum cut in directed planar networks
JO  - Kybernetika
PY  - 1992
SP  - 37
EP  - 49
VL  - 28
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_1992_28_1_a2/
LA  - en
ID  - KYB_1992_28_1_a2
ER  - 
%0 Journal Article
%A Janiga, Ladislav
%A Koubek, Václav
%T Minimum cut in directed planar networks
%J Kybernetika
%D 1992
%P 37-49
%V 28
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_1992_28_1_a2/
%G en
%F KYB_1992_28_1_a2
Janiga, Ladislav; Koubek, Václav. Minimum cut in directed planar networks. Kybernetika, Tome 28 (1992) no. 1, pp. 37-49. http://geodesic.mathdoc.fr/item/KYB_1992_28_1_a2/

[1] A.V. Aho J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. 1974. | MR

[2] E. W. Dijkstra: A note on two problems in connections with graphs. Numer. Math. 1 (1959), 269 - 271. | MR

[3] P. van Emde Boas R. Kaas, E. Zijlstra: Design and implementation of an efficient priority queue. Math. Systems Theory 10 (1977), 99 - 127. | MR

[4] L. R. Ford, D.R. Fulkerson: Flows in Networks. Princeton University Press, Princeton, N.J. 1962. | MR | Zbl

[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. | MR

[6] L. M. Fredman, D. E. Willard: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In: Proc. 31st FOCS, 1990, pp. 719 - 725.

[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. | MR | Zbl

[8] J. E. Hopcroft, R. E. Tarjan: Efficient planarity testing. J. Assoc. Comput. Mach. 21 (1974), 549 - 568. | MR | Zbl

[9] A. Itai, Y. Shiloach: Maximum flow in planar networks. SIAM J. Comput. 8 (1979), 135 - 150. | MR | Zbl

[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. | MR

[11] D.B. Johnson, S. Venkatesan: Using divide and conquer to find flows in directed planar networks in $O(n^{15}\log(n))$ time. In: 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. | MR | Zbl

[13] O. Ore: Theory of Graphs. Amer. Math. Soc. Coll. Publ., Vol. XXXVIII, Providence, R.I. 1962. | MR | Zbl

[14] J. H. Reif: Minimum S-T cut of a planar undirected network on $O(n \log^{2} (n))$ time. In: Automata, Languages and Programming (S. Even, D. Kariv, eds., Lecture Notes in Computer Science 115), Springer-Verlag, Berlin - Heidelberg - New York - Tokio 1981, pp. 56 - 67. | MR