{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T00:43:55Z","timestamp":1764377035389,"version":"3.46.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:00:00Z","timestamp":1742601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:00:00Z","timestamp":1742601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006356","name":"University of Southern Denmark","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006356","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This paper considers the well-known Travelling Salesman Problem (TSP) in its symmetric and asymmetric versions. A distinctive feature of the symmetric version of the problem is the ability to formulate it as an undirected network optimization problem using\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n(n - 1)\/2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    binary variables, where\n                    <jats:italic>n<\/jats:italic>\n                    is the number of locations involved in the problem. At the same time, formulating the asymmetric version of the problem generally requires the full set of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n(n - 1)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    binary variables. This paper presents a new approach to formulate the symmetric and asymmetric TSPs based on the flow of two commodities. Unlike traditional approaches formulating the problem with the flow of multiple commodities, the flow of two commodities considered in this paper is organized in opposite directions along a Hamiltonian cycle in the complete graph with\n                    <jats:italic>n<\/jats:italic>\n                    nodes. The proposed two-commodity network flow formulations are strictly stronger than their one-commodity flow counterparts in terms of the quality of their linear programming relaxations. This is a new result in the sense that the existing two-commodity network flow formulations of the TSP provide lower bounds that are no different from those of the corresponding one-commodity flow formulations. Moreover, the opposite direction flow of two commodities allows us to formulate the asymmetric TSP with only\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n(n - 1)\/2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    binary variables, just as in the case of symmetric TSP. This result suggests that various classes of valid inequalities based upon the polyhedral structure of the symmetric problem are sufficient for designing branch-and-cut algorithms for the asymmetric problem. Finally, the proposed mathematical programming formulations are compared to the existing approaches analytically and using an extensive computational study.\n                  <\/jats:p>","DOI":"10.1007\/s10589-025-00660-5","type":"journal-article","created":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T08:05:22Z","timestamp":1742717122000},"page":"987-1033","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Two-commodity opposite direction network flow formulations for the travelling salesman problem"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3345-5058","authenticated-orcid":false,"given":"Konstantin","family":"Pavlikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0002-2264","authenticated-orcid":false,"given":"Niels Christian","family":"Petersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,22]]},"reference":[{"issue":"2","key":"660_CR1","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498\u2013516 (1973)","journal-title":"Oper. Res."},{"issue":"1","key":"660_CR2","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106\u2013130 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"660_CR3","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","volume":"15","author":"D Applegate","year":"2003","unstructured":"Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for large traveling salesman problems. Informs J. Comput. 15(1), 82\u201392 (2003)","journal-title":"Informs J. Comput."},{"key":"660_CR4","doi-asserted-by":"crossref","unstructured":"Braun, H.: On solving travelling salesman problems by genetic algorithms. In: International Conference on Parallel Problem Solving from Nature, pp. 129\u2013133. Springer (1990)","DOI":"10.1007\/BFb0029743"},{"issue":"3","key":"660_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(92)00033-I","volume":"51","author":"C-N Fiechter","year":"1994","unstructured":"Fiechter, C.-N.: A parallel tabu search algorithm for large traveling salesman problems. Discrete Appl. Math. 51(3), 243\u2013267 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"660_CR6","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/0305-0548(94)90016-7","volume":"21","author":"J Knox","year":"1994","unstructured":"Knox, J.: Tabu search performance on the symmetric traveling salesman problem. Comput. Oper. Res. 21(8), 867\u2013876 (1994)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"660_CR7","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1287\/opre.2017.1603","volume":"65","author":"A Asadpour","year":"2017","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log n\/log log n)-approximation algorithm for the asymmetric traveling salesman problem. Oper. Res. 65(4), 1043\u20131061 (2017)","journal-title":"Oper. Res."},{"issue":"1","key":"660_CR8","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"660_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1057\/jors.2009.76","volume":"61","author":"G Laporte","year":"2010","unstructured":"Laporte, G.: A concise guide to the traveling salesman problem. J. Oper. Res. Soc. 61(1), 35\u201340 (2010)","journal-title":"J. Oper. Res. Soc."},{"key":"660_CR10","volume-title":"The Traveling Salesman Problem: a Computational Study","author":"DL Applegate","year":"2007","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: a Computational Study. Princeton University Press, USA (2007)"},{"issue":"1","key":"660_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.orl.2008.09.006","volume":"37","author":"DL Applegate","year":"2009","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W., Espinoza, D.G., Goycoolea, M., Helsgaun, K.: Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 37(1), 11\u201315 (2009)","journal-title":"Oper. Res. Lett."},{"key":"660_CR12","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com (2020)"},{"issue":"5","key":"660_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H Crowder","year":"1980","unstructured":"Crowder, H., Padberg, M.W.: Solving large-scale symmetric travelling salesman problems to optimality. Manag. Sci. 26(5), 495\u2013509 (1980)","journal-title":"Manag. Sci."},{"issue":"4","key":"660_CR14","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. Am."},{"issue":"1","key":"660_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"issue":"1","key":"660_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1080\/00207540310001601073","volume":"42","author":"E Duman","year":"2004","unstructured":"Duman, E., Or, I.: Precedence constrained TSP arising in printed circuit board assembly. Int. J. Prod. Res. 42(1), 67\u201378 (2004)","journal-title":"Int. J. Prod. Res."},{"issue":"2","key":"660_CR17","first-page":"77","volume":"48","author":"L Gouveia","year":"2006","unstructured":"Gouveia, L., Pesneau, P.: On extended formulations for the precedence constrained asymmetric traveling salesman problem. Netw. Int. J. 48(2), 77\u201389 (2006)","journal-title":"Netw. Int. J."},{"issue":"1","key":"660_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0167-6377(91)90083-2","volume":"10","author":"M Desrochers","year":"1991","unstructured":"Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1), 27\u201336 (1991)","journal-title":"Oper. Res. Lett."},{"issue":"7","key":"660_CR19","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1002\/net.3230230706","volume":"23","author":"A Langevin","year":"1993","unstructured":"Langevin, A., Desrochers, M., Desrosiers, J., G\u00e9linas, S., Soumis, F.: A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23(7), 631\u2013640 (1993)","journal-title":"Networks"},{"issue":"3","key":"660_CR20","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/PL00011432","volume":"90","author":"N Ascheuer","year":"2001","unstructured":"Ascheuer, N., Fischetti, M., Gr\u00f6tschel, M.: Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math. Program. 90(3), 475\u2013506 (2001)","journal-title":"Math. Program."},{"issue":"2","key":"660_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.orl.2020.01.008","volume":"48","author":"Y Yuan","year":"2020","unstructured":"Yuan, Y., Cattaruzza, D., Ogier, M., Semet, F.: A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows. Oper. Res. Lett. 48(2), 167\u2013169 (2020)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"660_CR22","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0377-2217(85)90284-X","volume":"20","author":"R Kulkarni","year":"1985","unstructured":"Kulkarni, R., Bhave, P.R.: Integer programming formulations of vehicle routing problems. Eur. J. Oper. Res. 20(1), 58\u201367 (1985)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"660_CR23","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1016\/S0377-2217(03)00377-1","volume":"158","author":"I Kara","year":"2004","unstructured":"Kara, I., Laporte, G., Bektas, T.: A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem. Eur. J. Oper. Res. 158(3), 793\u2013795 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"660_CR24","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1287\/opre.1040.0111","volume":"52","author":"R Baldacci","year":"2004","unstructured":"Baldacci, R., Hadjiconstantinou, E., Mingozzi, A.: An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5), 723\u2013738 (2004)","journal-title":"Oper. Res."},{"issue":"2","key":"660_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0377-2217(94)90360-3","volume":"79","author":"G Mosheiov","year":"1994","unstructured":"Mosheiov, G.: The travelling salesman problem with pick-up and delivery. Eur. J. Oper. Res. 79(2), 299\u2013310 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"660_CR26","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.dam.2003.09.013","volume":"145","author":"H Hern\u00e1ndez-P\u00e9rez","year":"2004","unstructured":"Hern\u00e1ndez-P\u00e9rez, H., Salazar-Gonz\u00e1lez, J.-J.: A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Disc. Appl. Math. 145(1), 126\u2013139 (2004)","journal-title":"Disc. Appl. Math."},{"key":"660_CR27","doi-asserted-by":"crossref","unstructured":"Pulleyblank, W.R.: Chapter V Polyhedral Combinatorics. In: Handbooks in Operations Research and Management Science, vol. 1, pp. 371\u2013446 (1989)","DOI":"10.1016\/S0927-0507(89)01006-6"},{"key":"660_CR28","unstructured":"Gavish, B., Graves, S.C.: The Travelling Salesman Problem and Related Problems, Working Paper OR 078\u201378, Massachusetts Institute of Technology, Operations Research Center, Boston (1978)."},{"issue":"2","key":"660_CR29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0167-6377(90)90052-7","volume":"9","author":"A Langevin","year":"1990","unstructured":"Langevin, A., Soumis, F., Desrosiers, J.: Classification of travelling salesman problem formulations. Oper. Res. Lett. 9(2), 127\u2013132 (1990)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"660_CR30","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1016\/j.cor.2007.11.008","volume":"36","author":"T \u00d6ncan","year":"2009","unstructured":"\u00d6ncan, T., Alt\u0131nel, \u0130K., Laporte, G.: A comparative analysis of several asymmetric traveling salesman problem formulations. Comput. Oper. Res. 36(3), 637\u2013654 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"1\u20132","key":"660_CR31","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s13676-012-0010-0","volume":"1","author":"R Roberti","year":"2012","unstructured":"Roberti, R., Toth, P.: Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO J. Transp. Logist. 1(1\u20132), 113\u2013133 (2012)","journal-title":"EURO J. Transp. Logist."},{"key":"660_CR32","first-page":"93","volume":"9","author":"A Orman","year":"2006","unstructured":"Orman, A., Williams, H.P.: A survey of different integer programming formulations of the travelling salesman problem. Optim. Econom. Financ. Anal. 9, 93\u2013108 (2006)","journal-title":"Optim. Econom. Financ. Anal."},{"issue":"1","key":"660_CR33","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia, L., Vo\u00df, S.: A classification of formulations for the (time-dependent) traveling salesman problem. Eur. J. Oper. Res. 83(1), 69\u201382 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"660_CR34","first-page":"167","volume":"41","author":"G Finke","year":"1984","unstructured":"Finke, G., Claus, A., Gunn, E.: A two-commodity network flow approach to the traveling salesman problem. Congr. Numer. 41, 167\u2013178 (1984)","journal-title":"Congr. Numer."},{"issue":"3","key":"660_CR35","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.orl.2003.08.005","volume":"32","author":"P Marcotte","year":"2004","unstructured":"Marcotte, P., Savard, G., Semet, F.: A bilevel programming approach to the travelling salesman problem. Oper. Res. Lett. 32(3), 240\u2013248 (2004)","journal-title":"Oper. Res. Lett."},{"key":"660_CR36","unstructured":"Wong, R.T.: Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE International Conference of Circuits and Computers, pp. 149\u2013152 . IEEE Press Piscataway NJ.(1980)"},{"issue":"1","key":"660_CR37","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1137\/0605004","volume":"5","author":"A Claus","year":"1984","unstructured":"Claus, A.: A new formulation for the travelling salesman problem. SIAM J. Algebr. Discrete Methods 5(1), 21\u201325 (1984)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"4","key":"660_CR38","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326\u2013329 (1960)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"660_CR39","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1287\/opre.50.4.656.2865","volume":"50","author":"HD Sherali","year":"2002","unstructured":"Sherali, H.D., Driscoll, P.J.: On tightening the relaxations of Miller-Tucker-Zemlin formulations for asymmetric traveling salesman problems. Oper. Res. 50(4), 656\u2013669 (2002)","journal-title":"Oper. Res."},{"issue":"1","key":"660_CR40","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/S0377-2217(97)00358-5","volume":"112","author":"L Gouveia","year":"1999","unstructured":"Gouveia, L., Pires, J.M.: The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints. Eur. J. Oper. Res. 112(1), 134\u2013146 (1999)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"660_CR41","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.orl.2004.03.007","volume":"33","author":"SC Sarin","year":"2005","unstructured":"Sarin, S.C., Sherali, H.D., Bhootra, A.: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper. Res. Lett. 33(1), 62\u201370 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"660_CR42","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.disopt.2005.10.004","volume":"3","author":"HD Sherali","year":"2006","unstructured":"Sherali, H.D., Sarin, S.C., Tsai, P.-F.: A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints. Discrete Optim. 3(1), 20\u201332 (2006)","journal-title":"Discrete Optim."},{"key":"660_CR43","unstructured":"Petersen, N.C.: The embedding of flow formulations of the TSP and some of its extensions into benders\u2019 decomposition algorithm: a practical approach for the solution of the TSP and a class of related routing problems to optimality in GAMS. Department of Management, University of Southern Denmark, Denmark (2000)"},{"key":"660_CR44","unstructured":"Santos, H.G., Toffolo, T.: Mixed integer linear programming with Python. Technical report (2020)"},{"issue":"4","key":"660_CR45","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB - a traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"issue":"4","key":"660_CR46","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"660_CR47","unstructured":"Hagberg, A., Swart, P., S\u00a0Chult, D.: Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008)"},{"key":"660_CR48","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01582226","volume":"67","author":"H Nagamochi","year":"1994","unstructured":"Nagamochi, H., Ono, T., Ibaraki, T.: Implementing an efficient minimum capacity cut algorithm. Math. Program. 67, 325\u2013341 (1994)","journal-title":"Math. Program."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00660-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-025-00660-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00660-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T10:28:09Z","timestamp":1764325689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-025-00660-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,22]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["660"],"URL":"https:\/\/doi.org\/10.1007\/s10589-025-00660-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2025,3,22]]},"assertion":[{"value":"5 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}