Review ArticleNo Access

Minimum Flows in Directed $1 - n$ Planar Static and Dynamic Networks with Arcs and Nodes Capacities

Department of Mathematics and Computer Science, Transilvania University of Braşov, Str. Iuliu Maniu, nr. 50, Braşov, 500091, România

E-mail Address: e.ciurea@unitbv.ro

Search for more papers by this author

Oana Georgescu

National College of Computer Science “Grigore Moisil” Braşov, str. Calea Bucureşti, nr. 75, Braşov, 500326, România

E-mail Address: o.georgescu@unitbv.ro

Search for more papers by this author

, and

Camelia Schiopu

Department of Management and Economic Informatics, Transilvania University of Braşov, Str. Colina Universităţii, nr. 1, Braşov, România

E-mail Address: camelia.s@unitbv.ro

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218126622300045Cited by:0 (Source: Crossref)

Abstract

Planar networks are an important special class of networks that arise in several application contexts. Because of the special structure of planar networks, network flow algorithms often run faster on these networks than they do on more general networks. In first part (Secs. 2–5), we present an algorithm for finding maximum cut and an algorithm for finding minimum flow in directed $1 - n$ planar static networks with arcs and nodes capacities. This part is presented in Ciurea et al. [Proc. 5th Int. Conf. Control Decision and Information Technologies (CoDIT2018), Thessaloniki, Greece (2018), pp. 110–115]. In the second part (Secs. 6–8), we present this problem in directed $1 - n$ planar dynamic networks with arcs and nodes capacities.

This paper was recommended by Regional Editor Piero Malcovati.

Keywords:

References

1. A. Ahuja, T. Magnanti and J. Orlin , Network Flows: Theory, Algorithms and Applications (Prentice Hall, Inc., Englewood Cliffs, NY, 1993). Google Scholar
2. J. A. Bondy and U. S. R. Murty , Graph Theory with Applications (North-Holland, Amsterdam, 1977). Google Scholar
3. G. Borradaile and P. N. Klein , An $O (n log n)$ algorithm for maximum $1 - n$ flow in a directed planar graph, J. ACM 56 (2009) 1–30. Crossref, Web of Science, Google Scholar
4. G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum and C. Wulf-Nilsen , Multiple-source multiple-sink maximum flow in directed planar graph in near-linear time, Proc. 52nd Annual Symp. Foundations of Computer Science (2011), pp. 170–179. Crossref, Google Scholar
5. X. Cai, D. Sha and C. Wong , Time-varying Network Optimization (Springer, 2007). Google Scholar
6. E. Ciurea and L. Ciupală , Sequential and parallel algorithms for minimum flows, J. Appl. Math. Comput. 15 (2004) 53–75. Crossref, Google Scholar
7. E. Ciurea and O. Georgescu , Minimum flows in directed $s - t$ planar networks, Bull. Math. Soc. Sci. Math. Roum. 53 (2010) 305–313. Google Scholar
8. E. Ciurea, O. Georgescu and C. Schiopu , Minimum flows in directed $s - t$ planar networks with arcs and nodes capacities, Proc. 5th Int. Conf. Control Decision and Information Technologies (CoDIT2018), Thessaloniki, Greece (2018), pp. 110–115. Crossref, Google Scholar
9. G. Demoucron, Y. Malgrange and R. Pertuiset , Graphes planaures: Reconnaissance et construction de representation planaires topologiques, Rev. Fr. Inform. Rech. Opr. 9 (1964) 33–47. Google Scholar
10. L. R. Ford and D. R. Fulkerson , Maximal flow through a network, Canad. J. Math. 8 (1956) 399–404. Crossref, Google Scholar
11. G. N. Frederickson , Fast algorithms for shortest paths in planar graphs with application, SIAM J. Comput. 16 (1987) 1004–1022. Crossref, Web of Science, Google Scholar
12. O. Georgescu , Minimum flow in network using dynamic tree implementation, Proc. 3rd Annual South-East European Doctoral Student Conf., Greece, Vol. 2 (2008), pp. 192–204. Google Scholar
13. R. Hassin , Maximum flows in $(s, t)$ planar networks, Inf. Process. Lett. 13 (1981) 107–117. Crossref, Web of Science, Google Scholar
14. R. Hassin and D. B. Johnson , An $O (n {log}^{2} n)$ algorithm for maximum flow in undirected planar networks, SIAM J. Comput. 14 (1985) 612–624. Crossref, Web of Science, Google Scholar
15. M. R. Henzinger, P. N. Klein, S. Rao and S. Subramanian , Faster shortestpath algorithms for planar graphs, J. Comput. Syst. Sci. 55 (1997) 3–23. Crossref, Web of Science, Google Scholar
16. A. Itai and Y. Shiloach , Maximum flow in planar networks, SIAM J. Comput. 8 (1979) 135–150. Crossref, Web of Science, Google Scholar
17. D. B. Johnson and S. Venkatesan , Using divide and conquer to find flows in directed planar networks in O( $n^{1.5} log n$ ) time, Proc. 20th Annual Allerton Conf. Communication, Control and Computing, University of Illinois Urbana-Champaign, IL (1982), pp. 898–905. Google Scholar
18. P. N. Klein , Multiple-sources shortest path in planar graphs, in Proc. 16th Annual ACM-SIAM Symp. Discrete Algorithm (2005), pp. 146–155. Google Scholar
19. P. N. Klein and S. Subramanian , A fully dynamic approximation scheme for shortest paths in planar graph, Algorithmica 22 (1998) 235–249. Crossref, Web of Science, Google Scholar
20. S. Khuller and J. Naor , Flows in planar graph with vertex capacities, Algorithmica 11 (1994) 200–225. Crossref, Web of Science, Google Scholar
21. R. J. Lipton and R. E. Tarjan , A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177–189. Crossref, Web of Science, Google Scholar
22. G. L. Miller , Finding small simple cycle separators for 2-connected planar graphs, J. Comput. Sci. 32 (1986) 265–279. Google Scholar
23. G. L. Miller and J. Naor , Flow in planar graphs with multiple sources and sinks, SIAM J. Comput. 24 (1995) 1002–1017. Crossref, Web of Science, Google Scholar
24. S. Mozes and C. Wulff-Nilsen , Shortest path in planar graphs with real lengths in $O (n {log}^{2} n ∕ log log n$ time, Proc. 18th European Symp. Algorithms, Liverpool, UK (2010), pp. 206–217. Google Scholar
25. C. Schiopu and E. Ciurea , The maximum flows in planar dynamic networks, Int. J. Comput. Commun. Control 11 (2016) 282–291. Crossref, Web of Science, Google Scholar
26. C. Schiopu , The maximum flows in bipartite dynamic networks: The static approach, Ann. Univ. Craiova Math. Comput. Sci. Ser. 43 (2016) 200–209. Google Scholar