Maximum Flows in Planar Dynamic Networks with Lower Bounds

• Autorzy: Schiopu C. , Ciurea E.

Identyfikatory

DOI

10.3233/FI-2018-1737

• Języki publikacji: EN

Abstrakty

EN

This article states and solves the maximum flow in directed (1, n) planar dynamic networks with lower bounds. We present the case when the planar dynamic network is stationary. Finally, we present an example for this problem.

Słowa kluczowe

EN

maximum flow; planar network; dynamic network; lower bounds

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 2
• Strony: 189--204
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Schiopu C.

• Department of Mathematics and Computer Science, Transilvania University of Braşov, 50 Iuliu Maniu, Braşov, 500091, Romania

autor

Ciurea E.

• Department of Mathematics and Computer Science, Transilvania University of Braşov, 50 Iuliu Maniu, Braşov, 500091, Romania

Bibliografia

• [1] Ahuja R, Magnanti T, Orlin J. Network flows. Theory, algorithms and applications. Prentice Hall, Inc., 1993. ISBN-10:013617549X, 13:978-0136175490.
• [2] Ford L, Fulkerson D. Flows in Networks. Princenton University Press, 1962.
• [3] Itai A, Shiloach Y. Maximum flow in planar networks. SIAM Journal on Computing, 1979. 8:135-150. URL https://doi.org/10.1137/0208012.
• [4] Hassin R. Maximum flow in (s,t) planar networks. Information Processing Letters, 1981.13:107.
• [5] Johnson D, Venkatesan S. Using divide and conquer to find flows in directed planar networks in O(n1:5logn) time. Proceedings of the 20th Annual Allerton Conference on Communication, Control and Computing, 1982. 8:898-905.
• [6] Hassin R, Johnson D. An O(nlog2n) algorithm for maximum flow in undirected planar networks. SIAM Journal on Computing, 1985. 14(3):612-624. URL https://doi.org/10.1137/0214045.
• [7] Khuller S, Naor J. Flows in planar graphs with vertex capacities. Algorithmica, 1994. 11(11):200-225. doi:10.1007/BF01240733.
• [8] Borradaile G, Klein P. An O(nlogn) algorithm for maximum st-flow in a directed planar graph. J. ACM, 2009. 56(2):1-30. doi:10.1145/1502793.1502798.
• [9] Cai X, Sha C Dand Wong. Time-varying Network Optimization. Springer, 2007. doi:10.1007/0-387-71215-1.
• [10] Ciurea E. An algorithm for minimal dynamic flow. Korean Journal of Computational and Applied Mathematics, 2000. 7(2):259-270. doi:/10.1007/BF03012192.
• [11] Wilkinson W. An Algorithm for Universal maximal Dynamic Flows in a Network. Oper. Res., 1971. 19(7):1602-1612. URL https://doi.org/10.1287/opre.19.7.1602.
• [12] Ciurea E, Georgescu O. Minimum flows in directed s-t planar networks. Bult. Math. de la Soc. des Scien. Math. de Roumanie, 2010. 101(4):305-313. URL https://www.jstor.org/stable/43679190.