{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:46:47Z","timestamp":1760143607775,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,18]],"date-time":"2024-02-18T00:00:00Z","timestamp":1708214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>In this paper, the generalized widest path problem (or generalized maximum capacity problem) is studied. This problem is denoted by the GWPP. The classical widest path problem is to find a path from a source (s) to a sink (t) with the highest capacity among all possible s-t paths. The GWPP takes into account the presence of loss\/gain factors on arcs as well. The GWPP aims to find an s-t path considering the loss\/gain factors while satisfying the capacity constraints. For solving the GWPP, three strongly polynomial time algorithms are presented. Two algorithms only work in the case of losses. The first one is less efficient than the second one on a CPU, but it proves to be more efficient on large networks if it parallelized on GPUs. The third algorithm is able to deal with the more general case of losses\/gains on arcs. An example is considered to illustrate how each algorithm works. Experiments on large networks are conducted to compare the efficiency of the algorithms proposed.<\/jats:p>","DOI":"10.3390\/axioms13020127","type":"journal-article","created":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T03:18:38Z","timestamp":1708312718000},"page":"127","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Widest Path in Networks with Gains\/Losses"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7559-3870","authenticated-orcid":false,"given":"Javad","family":"Tayyebi","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering, Birjand University of Technology, Industry and Mining Boulevard, Ibn Hesam Square, Birjand 9719866981, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihai-Lucian","family":"R\u00eetan","sequence":"additional","affiliation":[{"name":"Depatment of Mathematics and Computer Science, Transilvania University of Bra\u015fov, Eroilor St. 29, 500036 Bra\u015fov, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1070-1383","authenticated-orcid":false,"given":"Adrian Marius","family":"Deaconu","sequence":"additional","affiliation":[{"name":"Depatment of Mathematics and Computer Science, Transilvania University of Bra\u015fov, Eroilor St. 29, 500036 Bra\u015fov, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. Appl. Math."},{"key":"ref_3","unstructured":"Ford, L.R., and Fulkerson, D.R. (1962). A Shortest Chain Algorithm: Flows in Networks, Princeton University Press."},{"key":"ref_4","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows, Prentice Hall."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1016\/0377-2217(91)90073-5","article-title":"A linear time algorithm for the maximum capacity path problem","volume":"53","author":"Punnen","year":"1991","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1287\/trsc.21.2.115","article-title":"Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations","volume":"21","author":"Berman","year":"1987","journal-title":"Transp. Sci."},{"key":"ref_7","unstructured":"Kaibel, V., and Peinhardt, M.A.F. (2006). On the Bottleneck Shortest Path Problem, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin. ZIB-Report 06-22."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","article-title":"Algorithms for two bottleneck optimization problems","volume":"9","author":"Gabow","year":"1988","journal-title":"J. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s00355-010-0475-4","article-title":"A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method","volume":"36","author":"Schulze","year":"2011","journal-title":"Soc. Choice Welf."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1287\/opre.46.3.293","article-title":"Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths","volume":"46","author":"Fernandez","year":"1998","journal-title":"Oper. Res."},{"key":"ref_11","unstructured":"Ullah, E., Lee, K., and Hassoun, S. (2009, January 2\u20135). An algorithm for identifying dominant-edge metabolic pathways. Proceedings of the 2009 IEEE\/ACM International Conference on Computer-Aided Design-Digest of Technical Papers, San Jose, CA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Deaconu, A.M., Ciupala, L., and Spridon, D. (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"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"JACM"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tayyebi, J., R\u00eetan, M.-L., and Deaconu, A.M. (2024, January 24\u201326). Generalized Maximum Capacity Path Problem with Loss Factors. Proceedings of the 13th International Conference on Operations Research and Enterprise Systems (ICORES 2024), Rome, Italy. ISSN 2184-4372.","DOI":"10.5220\/0012387900003639"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Tayyebi, J., and Deaconu, A. (2019). Inverse generalized maximum flow problems. Mathematics, 7.","DOI":"10.3390\/math7100899"},{"key":"ref_17","unstructured":"Moore, E.F. (1959). Proceedings of the International Symposium on the Theory of Switching, Harvard University Press."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ortega-Arranz, H., Torres, Y., Llanos, D.R., and Gonzalez-Escribano, A. (2013, January 1\u20135). A new GPU-based approach to the Shortest Path problem. Proceedings of the 2013 International Conference on High Performance Computing & Simulation (HPCS), Helsinki, Finland.","DOI":"10.1109\/HPCSim.2013.6641461"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Deaconu, A.M., and Spridon, D. (2021). Adaptation of Random Binomial Graphs for Testing Network Flow Problems Algorithms. Mathematics, 9.","DOI":"10.3390\/math9151716"},{"key":"ref_20","first-page":"290","article-title":"On Random Graphs. I","volume":"6","year":"1959","journal-title":"Publ. Math."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/13\/2\/127\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:01:45Z","timestamp":1760104905000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/13\/2\/127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,18]]},"references-count":20,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["axioms13020127"],"URL":"https:\/\/doi.org\/10.3390\/axioms13020127","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2024,2,18]]}}}