{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:17:20Z","timestamp":1740107840126,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"23","license":[{"start":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T00:00:00Z","timestamp":1591747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T00:00:00Z","timestamp":1591747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004488","name":"Croatian Science Foundation","doi-asserted-by":"crossref","award":["IP-2018-01-5591"],"award-info":[{"award-number":["IP-2018-01-5591"]}],"id":[{"id":"10.13039\/501100004488","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00500-020-05063-8","type":"journal-article","created":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T12:02:41Z","timestamp":1591790561000},"page":"18073-18088","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Evolutionary operators for the Hamiltonian completion problem"],"prefix":"10.1007","volume":"24","author":[{"given":"Krunoslav","family":"Pulji\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0953-6517","authenticated-orcid":false,"given":"Robert","family":"Manger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,10]]},"reference":[{"key":"5063_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(00)00164-2","volume":"79","author":"A Agnetis","year":"2001","unstructured":"Agnetis A, Detti P, Meloni C, Pacciarelli D (2001) A linear algorithm for the Hamiltonian completion number of the line graph of a tree. Inf Process Lett 79:17\u201324","journal-title":"Inf Process Lett"},{"key":"5063_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1504\/IJPMB.2014.059449","volume":"4","author":"ZH Ahmed","year":"2014","unstructured":"Ahmed ZH (2014) Improved genetic algorithms for the traveling salesman problem. Int J Process Manag Benchmark 4:109\u2013124","journal-title":"Int J Process Manag Benchmark"},{"key":"5063_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0129054113500019","volume":"24","author":"M Bienkowski","year":"2013","unstructured":"Bienkowski M, Zalewski P (2013) (1,2)-Hamiltonian completion on a matching. Int J Found Comput S 24:95\u2013108","journal-title":"Int J Found Comput S"},{"key":"5063_CR4","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/S0305-0548(02)00050-3","volume":"30","author":"I Choi","year":"2003","unstructured":"Choi I, Kim S, Kim H (2003) A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Comput Oper Res 30:773\u2013786","journal-title":"Comput Oper Res"},{"key":"5063_CR5","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0137724","author":"C Contreras-Bolton","year":"2015","unstructured":"Contreras-Bolton C, Parada V (2015) Automatic combination of operators in a genetic algorithm to solve the traveling salesman problem. PLoS ONE. https:\/\/doi.org\/10.1371\/journal.pone.0137724","journal-title":"PLoS ONE"},{"key":"5063_CR6","volume-title":"In pursuit of the traveling salesman: mathematics at the limits of computation","author":"WJ Cook","year":"2012","unstructured":"Cook WJ (2012) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton"},{"key":"5063_CR7","unstructured":"Cook WJ (2015) Concorde TSP solver. University od Waterloo, Ontario, Canada. http:\/\/www.math.uwaterloo.ca\/tsp\/concorde\/index.html. Accessed 5 January 2020"},{"key":"5063_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(03)00441-4","volume":"136","author":"P Detti","year":"2004","unstructured":"Detti P, Meloni C (2004) A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. Discrete Appl Math 136:197\u2013215","journal-title":"Discrete Appl Math"},{"key":"5063_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10479-007-0231-z","volume":"156","author":"P Detti","year":"2007","unstructured":"Detti P, Meloni C, Pranzo M (2007) Local search algorithms for finding the Hamiltonian completion number of line graphs. Ann Oper Res 156:5\u201324","journal-title":"Ann Oper Res"},{"key":"5063_CR10","first-page":"296","volume":"220","author":"P Detti","year":"2013","unstructured":"Detti P, Meloni C, Pranzo M (2013) A lower bound on the Hamiltonian path completion number of a line graph. Appl Math Comput 220:296\u2013304","journal-title":"Appl Math Comput"},{"key":"5063_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44874-8","volume-title":"Introduction to evolutionary computing. Natural computing series","author":"AE Eiben","year":"2015","unstructured":"Eiben AE, Smith JE (2015) Introduction to evolutionary computing. Natural computing series, 2nd edn. Springer, Berlin","edition":"2"},{"key":"5063_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1017\/S1446181100013894","volume":"44","author":"DS Franzblau","year":"2002","unstructured":"Franzblau DS, Raychaudhuri A (2002) Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow. ANZIAM J 44:193\u2013204","journal-title":"ANZIAM J"},{"key":"5063_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.dam.2005.05.001","volume":"152","author":"D Gamarnik","year":"2005","unstructured":"Gamarnik D, Sviridenko M (2005) Hamiltonian completions of sparse random graphs. Discrete Appl Math 152:139\u2013158","journal-title":"Discrete Appl Math"},{"key":"5063_CR14","volume-title":"Computers and intractability: a guide to the theory of NP-completness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completness. W.H Freeman, San Francisco"},{"key":"5063_CR15","unstructured":"Gog A, Chira C (2011) Comparative analysis of recombination operators in genetic algorithms for the traveling salesman problem. In: Corchado E, Kurzynski M, Wozniak M (eds) Hybrid artificial intelligent systems\u20146th international conference, HAIS 2011, Wroclaw, Poland, May 23\u201325, 2011, Proceedings part II. LNCS vol 6679. Springer, Berlin, pp 10\u201317"},{"key":"#cr-split#-5063_CR16.1","unstructured":"Grefenstette JJ, Gopal R, Rosmaita BJ, Van Gucht D (1985) Genetic algorithms for the traveling salesman problem. In: Grefenstette JJ"},{"key":"#cr-split#-5063_CR16.2","unstructured":"(ed) Proceedings of the 1st international conference on genetic algorithms, Pittsburgh PA, July 1985. Lawrence Erlbaum Associates, Mahwah NJ, pp 160-168"},{"key":"5063_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/b101971","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2007","unstructured":"Gutin G, Punnen AP (2007) The traveling salesman problem and its variations. Springer, New York"},{"key":"5063_CR18","unstructured":"Helsgaun K (2018) LKH Version 2.0.9. Roskilde University, Denmark. http:\/\/akira.ruc.dk\/\u00a0keld\/research\/LKH. Accessed 5 January 2020"},{"key":"5063_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32278-5","volume-title":"Graphs, networks and algorithms","author":"D Jungnickel","year":"2013","unstructured":"Jungnickel D (2013) Graphs, networks and algorithms, 4th edn. Springer, Berlin","edition":"4"},{"key":"5063_CR20","doi-asserted-by":"publisher","first-page":"1032","DOI":"10.1016\/j.disc.2006.03.022","volume":"306","author":"J Komlos","year":"2006","unstructured":"Komlos J, Szeweredi E (2006) Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math 306:1032\u20131038","journal-title":"Discrete Math"},{"key":"5063_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0166-218X(94)90022-1","volume":"54","author":"NM Korneyenko","year":"1994","unstructured":"Korneyenko NM (1994) Combinatorial algorithms on a class of graphs. Discrete Appl Math 54:215\u2013217","journal-title":"Discrete Appl Math"},{"key":"5063_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial optimization\u2014theory and algorithms","author":"B Korte","year":"2012","unstructured":"Korte B, Wygen J (2012) Combinatorial optimization\u2014theory and algorithms, 5th edn. Springer, Berlin","edition":"5"},{"key":"5063_CR23","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1023\/A:1006529012972","volume":"13","author":"P Larranaga","year":"1999","unstructured":"Larranaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S (1999) Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif Intell Rev 13:129\u2013170","journal-title":"Artif Intell Rev"},{"key":"5063_CR24","first-page":"178","volume":"3","author":"C Li","year":"2011","unstructured":"Li C, Zhan W, Xu J, Yang L (2011) Development of two assistant crossover operators to solve the traveling salesman problem. Int J Adv Comput Technol 3:178\u2013184","journal-title":"Int J Adv Comput Technol"},{"key":"#cr-split#-5063_CR25.1","doi-asserted-by":"crossref","unstructured":"Mareti\u0107 HP, Grbi\u0107 A (2015) A heuristic approach to Hamiltonian completion problem (HCP). In: Biljanovi\u0107 P","DOI":"10.1109\/MIPRO.2015.7160528"},{"key":"#cr-split#-5063_CR25.2","unstructured":"(ed) Proceedings of the 38th international convention on information and communication technology, electronics and microelectronics, MIPRO 2015, Opatija, Croatia, May 25-29, 2015. MIPRO Society, Rijeka, Croatia, pp 1607-1612"},{"key":"5063_CR26","doi-asserted-by":"crossref","unstructured":"Mchedlidze T, Symvonis A (2009) Crossing-optimal acyclic Hamiltonian path completion and its application to upward topological book embeddings. In: Das S, Uchara R (eds) Proceedings of the third international workshop on algorithms and computation, WALCOM 2009, Kolkata, India, February 18\u201320 (2009) LNCS, vol 5431. Springer, Berlin, pp 250\u2013261","DOI":"10.1007\/978-3-642-00202-1_22"},{"key":"5063_CR27","doi-asserted-by":"crossref","unstructured":"Mchedlidze T, Symvonis A (2009) Crossing-free acyclic Hamiltonian path completion for planar st-digraphs. In: Dong Y, Du D-Z, Ibarra O (eds) Proceedings of the 20th international symposium on algorithms and computation, ISAAC 2009, Honolulu, Hawaii, USA, December 16\u201318 (2009) LNCS, vol 5878. Springer, Berlin, pp 882\u2013891","DOI":"10.1007\/978-3-642-10631-6_89"},{"key":"5063_CR28","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s10479-006-0065-0","volume":"147","author":"C Meloni","year":"2006","unstructured":"Meloni C, Naso D, Turchiano B (2006) Setup coordination between two stages of a production system: a multi-objective evolutionary approach. Ann Oper Res 147:175\u2013198","journal-title":"Ann Oper Res"},{"key":"5063_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03315-9","volume-title":"Genetic algorithms + data structures = evolution programs","author":"Z Michalewicz","year":"1996","unstructured":"Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, New York","edition":"3"},{"key":"5063_CR30","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1287\/ijoc.1120.0506","volume":"25","author":"Y Nagata","year":"2013","unstructured":"Nagata Y, Kobayashi S (2013) A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J Comput 25:346\u2013363","journal-title":"INFORMS J Comput"},{"key":"5063_CR31","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10845-005-6641-3","volume":"17","author":"D Naso","year":"2006","unstructured":"Naso D, Turchiano B, Meloni C (2006) Single and multi-objective evolutionary algorithms for the coordination of serial manufacturing operations. J Intell Manuf 17:251\u2013270","journal-title":"J Intell Manuf"},{"key":"5063_CR32","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.jpdc.2003.08.004","volume":"64","author":"SD Nikolopolous","year":"2004","unstructured":"Nikolopolous SD (2004) Parallel algorithms for Hamiltonian problems on quasi-threshold graphs. J Parallel Distrib Comput 64:48\u201367","journal-title":"J Parallel Distrib Comput"},{"key":"5063_CR33","volume-title":"Combinatorial optimization: algorithms and complexity","author":"CH Papadimitrou","year":"1998","unstructured":"Papadimitrou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover Publications, Mineola"},{"key":"5063_CR34","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1080\/02664760120034162","volume":"28","author":"P Pongcharoen","year":"2001","unstructured":"Pongcharoen P, Stewardson DJ, Hicks C, Braiden PM (2001) Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry. J Appl Stat 28:441\u2013455","journal-title":"J Appl Stat"},{"key":"5063_CR35","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(95)00163-8","volume":"56","author":"A Raychaudhuri","year":"1995","unstructured":"Raychaudhuri A (1995) The total interval number of a tree and the Hamiltonian completion number of its line graph. Inf Process Lett 56:299\u2013306","journal-title":"Inf Process Lett"},{"key":"5063_CR36","unstructured":"Raychaudhuri A (1999) On Hamiltonian path completion number of an interval graph. In: Stanton RG, Allston JL (eds) Proceedings of the 30th southeastern international conference on combinatorics, graph theory and computing, Boca Raton, FL, March 8\u201312, 1999. Utilitas Mathematica Publishing, Winnipeg, Manitoba, Canada, pp 193\u2013198"},{"key":"5063_CR37","volume-title":"Schaum\u2019s outline of statistics","author":"M Spiegel","year":"2014","unstructured":"Spiegel M, Stephens L (2014) Schaum\u2019s outline of statistics, 5th edn. McGraw-Hill, New York","edition":"5"},{"key":"5063_CR38","unstructured":"Starkweather T, McDaniel S, Mathias KE, Whitley LD, Whitley C (1991) A comparison of genetic sequencing operators. In: Belew RK, Booker LB (eds) Proceedings of the 4th international conference on genetic algorithms, San Diego CA, July 1991. Morgan Kaufmann, San Francisco CA, pp 69\u201376"},{"key":"5063_CR39","doi-asserted-by":"publisher","first-page":"1718","DOI":"10.1109\/TSMCB.2004.828283","volume":"34","author":"HK Tsai","year":"2004","unstructured":"Tsai HK, Yang J-M, Tsai Y-F, Kao C-Y (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern B Cybern 34:1718\u20131729","journal-title":"IEEE Trans Syst Man Cybern B Cybern"},{"key":"5063_CR40","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/j.asoc.2016.02.021","volume":"43","author":"J Wang","year":"2016","unstructured":"Wang J, Ersoy OK, He M, Wang F (2016) Multi-offspring genetic algorithm and its application to the traveling salesman problem. Appl Soft Comput 43:415\u2013423","journal-title":"Appl Soft Comput"},{"key":"5063_CR41","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.dam.2018.07.014","volume":"254","author":"J Wang","year":"2019","unstructured":"Wang J, Yang W (2019) The Tur\u00e1n number for spanning linear forests. Discrete Appl Math 254:291\u2013294","journal-title":"Discrete Appl Math"},{"key":"5063_CR42","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.tcs.2005.03.043","volume":"341","author":"Q Wu","year":"2005","unstructured":"Wu Q, Lu CL, Lee RC-T (2005) The approximability of the weighted Hamiltonian path completion problem on a tree. Theor Comput Sci 341:385\u2013397","journal-title":"Theor Comput Sci"},{"key":"5063_CR43","first-page":"1","volume":"17","author":"Z Zhao","year":"2016","unstructured":"Zhao Z, Chen Y, Zhao Z (2016) A study on the traveling salesman problem using genetic algorithms. Int J Simul Syst Sci Technol 17:1\u20136","journal-title":"Int J Simul Syst Sci Technol"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-020-05063-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-020-05063-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-020-05063-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T23:41:07Z","timestamp":1623282067000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-020-05063-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,10]]},"references-count":45,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["5063"],"URL":"https:\/\/doi.org\/10.1007\/s00500-020-05063-8","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"type":"print","value":"1432-7643"},{"type":"electronic","value":"1433-7479"}],"subject":[],"published":{"date-parts":[[2020,6,10]]},"assertion":[{"value":"10 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}