{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T15:19:56Z","timestamp":1761664796828,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,5]],"date-time":"2025-02-05T00:00:00Z","timestamp":1738713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>This paper investigates the application of a minimum loss path finding algorithm to determine the maximum flow in generalized networks that are characterized by arc losses or gains. In these generalized network flow problems, each arc has not only a defined capacity but also a loss or gain factor, which must be taken into consideration when calculating the maximum achievable flow. This extension of the traditional maximum flow problem requires a more comprehensive approach, where the maximum amount of flow is determined by accounting for additional factors such as costs, varying arc capacities, and the specific loss or gain associated with each arc. This paper extends the classic Ford\u2013Fulkerson algorithm, adapting it to iteratively identify source-to-sink (s \u2212 t) residual directed paths with minimum cumulative loss and generalized augmenting paths (GAPs), thus enabling the efficient computation of maximum flow in such complex networks. Moreover, to enhance the computational performance of the proposed algorithm, we conducted extensive studies on parallelization techniques using graphics processing units (GPUs). Significant improvements in the algorithm\u2019s efficiency and scalability were achieved. The results demonstrate the potential of GPU-accelerated computations in handling real-world applications where generalized network flows with arc losses and gains are prevalent, such as in telecommunications, transportation, or logistics networks.<\/jats:p>","DOI":"10.3390\/computation13020040","type":"journal-article","created":{"date-parts":[[2025,2,5]],"date-time":"2025-02-05T10:09:52Z","timestamp":1738750192000},"page":"40","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Novel GPU-Based Method for the Generalized Maximum Flow Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-5057","authenticated-orcid":false,"given":"Delia Elena","family":"Spridon","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Transilvania University of Bra\u0219ov, 500036 Bra\u0219ov, Romania"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1070-1383","authenticated-orcid":false,"given":"Adrian Marius","family":"Deaconu","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Transilvania University of Bra\u0219ov, 500036 Bra\u0219ov, Romania"}]},{"given":"Javad","family":"Tayyebi","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Birjand University of Technology, Birjand 97198-66981, Iran"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,5]]},"reference":[{"key":"ref_1","unstructured":"Ahuja, R., Magnanti, T., and Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice Hall."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1287\/opre.10.4.476","article-title":"Optimal flow through networks with gains","volume":"10","author":"Jewell","year":"1962","journal-title":"Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Tardos, E., and Wayne, K. (1998, January 22\u201324). Simple generalized maximum flow. Integer Programming and Combinatorial Optimization. Proceedings of the 6th International IPCO Conference, Houston, TX, USA.","DOI":"10.1007\/3-540-69346-7_24"},{"key":"ref_4","unstructured":"Vegh, L. (2016, January 19\u201321). A strongly polynomial algorithm for generalized flow maximization. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Tayyebi, J., and Deaconu, A. (2019). Inverse generalized maximum flow problems. Mathematics, 8.","DOI":"10.3390\/math7100899"},{"key":"ref_6","unstructured":"Spridon, D.E., Deaconu, A.M., and Tayyebi, J. (2024, January 26\u201328). New approach for the Generalized Maximum Flow Problem. Proceedings of the International Conferences on Applied Computing, Zagreb, Croatia."},{"key":"ref_7","unstructured":"Koopmans, T.C. (1951). Application of the simplex method to a transportation problem. Activity Analysis of Production and Allocation, John Wiley and Sons."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/PL00009180","article-title":"On Implementing the Push\u2014Relabel Method for the Maximum Flow Problem","volume":"19","author":"Cherkassky","year":"1997","journal-title":"Algorithmica"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1287\/moor.16.2.351","article-title":"Combinatorial algorithms for the generalized circulation problem","volume":"16","author":"Goldberg","year":"1991","journal-title":"Math. Oper. Res."},{"key":"ref_11","unstructured":"Wayne, K. (2024, December 05). Generalized Maximum Flow Algorithms. Available online: https:\/\/www.cs.princeton.edu\/~wayne\/papers\/thesis.pdf."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Deaconu, A., Spridon, D., and Ciupala, L. (2023, January 10\u201312). Finding minimum loss path in big networks. Proceedings of the 22nd International Symposium on Parallel and Distributed Computing (ISPDC), Bucharest, Romania.","DOI":"10.1109\/ISPDC59212.2023.00012"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/2\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:27:22Z","timestamp":1760027242000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/2\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,5]]},"references-count":12,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["computation13020040"],"URL":"https:\/\/doi.org\/10.3390\/computation13020040","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2025,2,5]]}}}