| Title:
|
Minimum cut in directed planar networks (English) |
| Author:
|
Janiga, Ladislav |
| Author:
|
Koubek, Václav |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
28 |
| Issue:
|
1 |
| Year:
|
1992 |
| Pages:
|
37-49 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C85 |
| MSC:
|
90B10 |
| MSC:
|
90C35 |
| MSC:
|
90C60 |
| idZBL:
|
Zbl 0763.90084 |
| idMR:
|
MR1159873 |
| . |
| Date available:
|
2009-09-24T18:29:43Z |
| Last updated:
|
2012-06-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124970 |
| . |
| Reference:
|
[1] A.V. Aho J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms.Addison-Wesley, Reading, Mass. 1974. MR 0413592 |
| Reference:
|
[2] E. W. Dijkstra: A note on two problems in connections with graphs.Numer. Math. 1 (1959), 269 - 271. MR 0107609 |
| Reference:
|
[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 0431777 |
| Reference:
|
[4] L. R. Ford, D.R. Fulkerson: Flows in Networks.Princeton University Press, Princeton, N.J. 1962. Zbl 0106.34802, MR 0159700 |
| Reference:
|
[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 0904195 |
| Reference:
|
[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. |
| Reference:
|
[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, MR 0795934 |
| Reference:
|
[8] J. E. Hopcroft, R. E. Tarjan: Efficient planarity testing.J. Assoc. Comput. Mach. 21 (1974), 549 - 568. Zbl 0307.68025, MR 0359387 |
| Reference:
|
[9] A. Itai, Y. Shiloach: Maximum flow in planar networks.SIAM J. Comput. 8 (1979), 135 - 150. Zbl 0419.90040, MR 0529586 |
| Reference:
|
[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 0810105 |
| Reference:
|
[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. |
| Reference:
|
[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, MR 0756414 |
| Reference:
|
[13] O. Ore: Theory of Graphs.Amer. Math. Soc. Coll. Publ., Vol. XXXVIII, Providence, R.I. 1962. Zbl 0105.35401, MR 0150753 |
| Reference:
|
[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 0635129 |
| . |
