Minimum cut in directed planar networks

Ladislav Janiga; Václav Koubek

Kybernetika (1992)

  • Volume: 28, Issue: 1, page 37-49
  • ISSN: 0023-5954

How to cite

top

Janiga, Ladislav, and Koubek, Václav. "Minimum cut in directed planar networks." Kybernetika 28.1 (1992): 37-49. <http://eudml.org/doc/28125>.

@article{Janiga1992,
author = {Janiga, Ladislav, Koubek, Václav},
journal = {Kybernetika},
keywords = {planar directed network; minimum cut},
language = {eng},
number = {1},
pages = {37-49},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Minimum cut in directed planar networks},
url = {http://eudml.org/doc/28125},
volume = {28},
year = {1992},
}

TY - JOUR
AU - Janiga, Ladislav
AU - Koubek, Václav
TI - Minimum cut in directed planar networks
JO - Kybernetika
PY - 1992
PB - Institute of Information Theory and Automation AS CR
VL - 28
IS - 1
SP - 37
EP - 49
LA - eng
KW - planar directed network; minimum cut
UR - http://eudml.org/doc/28125
ER -

References

top
  1. A.V. Aho J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. 1974. (1974) MR0413592
  2. E. W. Dijkstra, A note on two problems in connections with graphs, Numer. Math. 1 (1959), 269 - 271. (1959) MR0107609
  3. P. van Emde Boas R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue, Math. Systems Theory 10 (1977), 99 - 127. (1977) MR0431777
  4. L. R. Ford, D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N.J. 1962. (1962) Zbl0106.34802MR0159700
  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. (1987) MR0904195
  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. (1990) 
  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. (1985) Zbl0565.90018MR0795934
  8. J. E. Hopcroft, R. E. Tarjan, Efficient planarity testing, J. Assoc. Comput. Mach. 21 (1974), 549 - 568. (1974) Zbl0307.68025MR0359387
  9. A. Itai, Y. Shiloach, Maximum flow in planar networks, SIAM J. Comput. 8 (1979), 135 - 150. (1979) Zbl0419.90040MR0529586
  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. (1985) MR0810105
  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. (1982) 
  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. (1984) Zbl0556.68002MR0756414
  13. O. Ore, Theory of Graphs, Amer. Math. Soc. Coll. Publ., Vol. XXXVIII, Providence, R.I. 1962. (1962) Zbl0105.35401MR0150753
  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. (1981) MR0635129

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.