Improved Parallel Algorithm for Finding Minimum Cuts in Stochastic Flow Networks

Authors

Keywords:

Connectivity, Reliability, Parallel Algorithm, Min-Cuts, Stochastic-Flow Networks, Network Reliability, Graph Theory

Abstract

This article solves the convergence problem in the Parallel BK algorithm for large-scale flow networks. We introduce a merging method and a pseudo-Boolean representation-based invariance analysis that optimize the algorithm's performance compared to classical approaches such as Ford-Fulkerson, Edmonds-Karp, Push-Relabel, and Karger’s Algorithm. Our approach improves energy efficiency, reduces memory usage, and lowers time complexity by leveraging parallelization techniques. We evaluate the performance of these algorithms using Python simulations on various benchmark graphs, ranging from small to large-scale networks. The results show that our method reduces memory consumption by up to 40\% and speeds up execution time by 30%, while maintaining high accuracy in finding minimum cuts. This paper demonstrates the algorithm's potential for applications in image segmentation, wireless sensor networks, and network reliability analysis

Downloads

Download data is not yet available.

Author Biographies

Mohammad Joshan , Federal University of Sao Carlos

Mohammad Joshan is pursuing his Master's degree in Computer Science from the Federal University of Sao Carlos (UFSCar), Brazil. His research interests include parallel algorithms, graph theory, and network flow optimization. He has contributed to the development of efficient parallel algorithms for solving minimum cut problems in large-scale networks.

José H. , Department of Computer Science, Federal University of Sao Carlos

Jose Saito holds a degree in Electrical Engineering from the Sao Carlos School of Engineering-University of Sao Paulo (EESC-USP) (1972), a master's degree in Electronic and Computer Engineering from the Technological Institute of Aeronautics (ITA) (1979) and a PhD in Electrical Engineering from the Polytechnic School of the University of Sao Paulo (EPUSP) (1983). He developed a Postdoctoral Program at Osaka University, with the Laboratory of Professor Kunihiko Fukushima, from August 1997 to February 1999. He is currently a professor in the Master's Program in Computer Science at the Campo Limpo Paulista University Center (UNIFACCAMP) and a collaborating professor at the Federal University of Sao Carlos (UFSCar). He has experience in Computer Science, with an emphasis on Computer Architectures and Neural Networks, working mainly on the following topics: convolutional neural networks, neocognitron, reconfigurable architectures and electrophysiological signal recording systems in microelectrode arrays. 

Emerson Carlos Pedrino, Federal University of Sao Carlos

Emerson Pedrino is an associate professor at the Federal University of Sao Carlos (UFSCar). He has a Ph.D. in Electrical Engineering and specializes in high-performance computing, network flow analysis, and algorithm optimization. His research contributions include advancements in graph-based optimization methods.

References

REFERENCES

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory,

Algorithms, and Applications, Prentice Hall, 1993. https://doi.org/10.2307/

S. Dasgupta, Experiments with Random Projection, arXiv preprint

arXiv:1301.3849, 2013. Available at: https://doi.org/10.48550/arXiv.1301.

J. Edmonds and R. M. Karp, ”Theoretical improvements in algorithmic

efficiency for network flow problems,” Journal of the ACM (JACM), vol.

, no. 2, pp. 248-264, 1972. Available at: https://doi.org/10.1145/321694.

R. Esheta, M. Dintzman, A. Pertzelana, and Z. Larona, ”Lessons from

Laron Syndrome (LS) 1966–1992,” in Laron Z, Parks JS (eds): Lessons

from Laron Syndrome (LS) 1966–1992. Pediatr Adolesc Endocrinol, vol.

, pp. 24-26, Basel, Karger, 1993. https://doi.org/10.1159/000419963

L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,”

Canadian Journal of Mathematics, vol. 8, pp. 399–404, 1956. Available

at: https://doi.org/10.4153/CJM-1956-045-5

M. Forghani-Elahabad and E. Francesquini, “An improved vectorization

algorithm to solve the d-MP problem,” Journal of Computational Mathe-

matics, 2023, received on December 23, 2021 / accepted on July 1, 2022.

Available at: https://doi.org/10.1017/S0956796823000056

O. Goldschmidt and D. S. Hochbaum, “A polynomial algorithm for the

k-cut problem for fixed k,” Mathematics of Operations Research, vol. 19,

no. 1, pp. 24–37, 1994. Available at: https://doi.org/10.1287/moor.19.1.24

A. V. Goldberg and R. E. Tarjan, ”A new approach to the maximum-flow

problem,” Journal of the ACM (JACM), vol. 35, no. 4, pp. 921-940, 1988.

Available at: https://doi.org/10.1145/48014.61051

P. M. Jensen, N. Jeppesen, A. B. Dahl, and V. A. Dahl, “Review of

serial and parallel min-cut/max-flow algorithms for computer vision,”

International Journal of Computer Vision, 2023. Available at: https://doi.

org/10.1007/s11263-023-01600-w

D. R. Karger, “Global min-cuts in RNC, and other ramifications of a

simple min-cut algorithm,” in Proceedings of the Fourth Annual ACM-

SIAM Symposium on Discrete Algorithms (SODA), pp. 21–30, 1993.

Available at: https://doi.org/10.5555/3149692.3149695

R. M. Karp, “Reducibility among combinatorial problems,” in Complex-

ity of Computer Computations, Springer, Boston, MA, pp. 85–103, 1972.

Available at: https://doi.org/10.1007/978-1-4684-2001-2 9

P. Kohli and P. H. S. Torr, ”Efficiently solving dynamic Markov

random fields using graph cuts,” International Journal of Computer Vision,

vol. 79, no. 2, pp. 202-224, 2008. Available at: https://doi.org/10.1007/

s11263-007-0128-5

V. Kolmogorov and R. Zabih, ”What energy functions can be min-

imized via graph cuts?” IEEE Transactions on Pattern Analysis and

Machine Intelligence, vol. 26, no. 2, pp. 147-159, 2004. Available at:

https://doi.org/10.1109/TPAMI.2004.1262177

A. D. Mwangi, Z. Jianhua, H. Gang, R. M. Kasomo, and I. M. Matidza,

”Ultimate pit limit optimization using Boykov-Kolmogorov maximum flow

algorithm,” Journal of Mining and Environment, vol. 12, no. 1, pp. 1-13,

Available at: https://doi.org/10.22044/jme.2020.10111.2000

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, vol.

, no. 2, Berlin: Springer, 2003. Available at: https://doi.org/10.1007/

-3-642-02253

Downloads

Published

2025-03-07

How to Cite

Joshan , M. ., Saito, J. H., & Pedrino, E. C. . (2025). Improved Parallel Algorithm for Finding Minimum Cuts in Stochastic Flow Networks. IEEE Latin America Transactions, 23(4), 285–293. Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/9379

Issue

Vol. 23 No. 4 (2025): Ordinary Issue

Section

Computing