{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T06:20:08Z","timestamp":1778739608932,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,7,1]],"date-time":"2020-07-01T00:00:00Z","timestamp":1593561600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,1]],"date-time":"2020-07-01T00:00:00Z","timestamp":1593561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds voor wetenschappelijk onderzoek","doi-asserted-by":"crossref","award":["S007318N"],"award-info":[{"award-number":["S007318N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003130","name":"Fonds voor wetenschappelijk onderzoek","doi-asserted-by":"crossref","award":["12P9419N"],"award-info":[{"award-number":["12P9419N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10732-020-09447-9","type":"journal-article","created":{"date-parts":[[2020,7,1]],"date-time":"2020-07-01T19:48:35Z","timestamp":1593632915000},"page":"743-769","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5256-1921","authenticated-orcid":false,"given":"Jorik","family":"Jooken","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3452-0413","authenticated-orcid":false,"given":"Pieter","family":"Leyman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6763-1945","authenticated-orcid":false,"given":"Patrick","family":"De Causmaecker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,1]]},"reference":[{"issue":"1","key":"9447_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W Ackermann","year":"1928","unstructured":"Ackermann, W.: Zum hilbertschen aufbau der reellen zahlen. Math. Ann. 99(1), 118\u2013133 (1928). https:\/\/doi.org\/10.1007\/BF01459088","journal-title":"Math. Ann."},{"issue":"1","key":"9447_CR2","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.: A linear algorithm for the Hamiltonian completion number of the line graph of a tree. Inf. Process. Lett. 79(1), 17\u201324 (2001). https:\/\/doi.org\/10.1016\/S0020-0190(00)00164-2","journal-title":"Inf. Process. Lett."},{"key":"9447_CR3","unstructured":"Applegate, D.: Concorde\u2014a code for solving traveling salesman problems (2001). http:\/\/www.math.princeton.edu\/tsp\/concorde.html"},{"key":"9447_CR4","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841103","volume-title":"The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics)","author":"DL Applegate","year":"2007","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton (2007)"},{"key":"9447_CR5","doi-asserted-by":"publisher","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13\u201314, 2012. Proceedings, Contemporary Mathematics, vol. 588. American Mathematical Society (2013). https:\/\/doi.org\/10.1090\/conm\/588","DOI":"10.1090\/conm\/588"},{"issue":"5439","key":"9447_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999). https:\/\/doi.org\/10.1126\/science.286.5439.509","journal-title":"Science"},{"key":"9447_CR7","doi-asserted-by":"publisher","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory, vol. 184 (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0619-4","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"9447_CR8","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-04918-7_13","volume-title":"Hybrid Metaheuristics","author":"MA Boschetti","year":"2009","unstructured":"Boschetti, M.A., Maniezzo, V., Roffilli, M., Boluf\u00e9 R\u00f6hler, A.: Matheuristics: optimization, simulation and control. In: Blesa, M.J., Blum, C., Di Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) Hybrid Metaheuristics, pp. 171\u2013177. Springer, Berlin (2009)"},{"key":"9447_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511703768","volume-title":"The Collected Mathematical Papers, Cambridge Library Collection\u2014Mathematics","author":"A Cayley","year":"2009","unstructured":"Cayley, A.: The Collected Mathematical Papers, Cambridge Library Collection\u2014Mathematics, vol. 10. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9780511703768"},{"issue":"2","key":"9447_CR10","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.: A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. Discrete Appl. Math. 136(2), 197\u2013215 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(03)00441-4","journal-title":"Discrete Appl. Math."},{"key":"9447_CR11","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.: Local search algorithms for finding the Hamiltonian completion number of line graphs. Ann. Oper. Res. 156, 5\u201324 (2007). https:\/\/doi.org\/10.1007\/s10479-007-0231-z","journal-title":"Ann. Oper. Res."},{"key":"9447_CR12","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On random graphs, I. Publ. Math. (Debrecen) 6, 290\u2013297 (1959)","journal-title":"Publ. Math. (Debrecen)"},{"issue":"2","key":"9447_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1017\/S1446181100013894","volume":"44","author":"DS Franzblau","year":"2002","unstructured":"Franzblau, D.S., Raychaudhuri, A.: Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow. ANZIAM J. 44(2), 193\u2013204 (2002). https:\/\/doi.org\/10.1017\/S1446181100013894","journal-title":"ANZIAM J."},{"issue":"1\u20133","key":"9447_CR14","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.: Hamiltonian completions of sparse random graphs. Discrete Appl. Math. 152(1\u20133), 139\u2013158 (2005). https:\/\/doi.org\/10.1016\/j.dam.2005.05.001","journal-title":"Discrete Appl. Math."},{"key":"9447_CR15","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"issue":"5","key":"9447_CR16","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Gomory, R.E.: Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper. Res. 12(5), 655\u2013679 (1964)","journal-title":"Oper. Res."},{"key":"9447_CR17","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BFb0066448","volume-title":"Graphs and Combinatorics","author":"S Goodman","year":"1974","unstructured":"Goodman, S., Hedetniemi, S.: On the Hamiltonian completion problem. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics, pp. 262\u2013272. Springer, Berlin (1974)"},{"issue":"3","key":"9447_CR18","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1145\/321892.321897","volume":"22","author":"SE Goodman","year":"1975","unstructured":"Goodman, S.E., Hedetniemi, S.T., Slater, P.J.: Advances on the Hamiltonian completion problem. J. ACM 22(3), 352\u2013360 (1975). https:\/\/doi.org\/10.1145\/321892.321897","journal-title":"J. ACM"},{"issue":"1","key":"9447_CR19","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\u2013Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106\u2013130 (2000). https:\/\/doi.org\/10.1016\/S0377-2217(99)00284-2","journal-title":"Eur. J. Oper. Res."},{"key":"9447_CR20","volume-title":"Using POPMUSIC for Candidate Set Generation in the Lin\u2013Kernighan\u2013Helsgaun TSP Solver","author":"K Helsgaun","year":"2018","unstructured":"Helsgaun, K.: Using POPMUSIC for Candidate Set Generation in the Lin\u2013Kernighan\u2013Helsgaun TSP Solver. Roskilde Universitet, Roskilde (2018)"},{"key":"9447_CR21","unstructured":"Jooken, J.: Combinatorische optimalisatie als een perturbatie. Master\u2019s thesis, Leuven (2019)"},{"key":"9447_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility Among Combinatorial Problems","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85\u2013103. Springer US, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"9447_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2898361","volume":"8","author":"J Leskovec","year":"2016","unstructured":"Leskovec, J., Sosi\u010d, R.: SNAP: a general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol: TIST 8(1), 1 (2016)","journal-title":"ACM Trans. Intell. Syst. Technol: TIST"},{"key":"9447_CR24","doi-asserted-by":"publisher","unstructured":"Maretic, H.P., Grbic, A.: A heuristics approach to Hamiltonian completion problem (hcp). In: 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), pp. 1607\u20131612 (2015). https:\/\/doi.org\/10.1109\/MIPRO.2015.7160528","DOI":"10.1109\/MIPRO.2015.7160528"},{"issue":"4","key":"9447_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L P\u00f3sa","year":"1976","unstructured":"P\u00f3sa, L.: Hamiltonian circuits in random graphs. Discrete Math. 14(4), 359\u2013364 (1976). https:\/\/doi.org\/10.1016\/0012-365X(76)90068-6","journal-title":"Discrete Math."},{"issue":"6","key":"9447_CR26","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.: The total interval number of a tree and the Hamiltonian completion number of its line graph. Inf. Process. Lett. 56(6), 299\u2013306 (1995). https:\/\/doi.org\/10.1016\/0020-0190(95)00163-8","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9447_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1080\/03052158708902546","volume":"10","author":"VJ Rayward-Smith","year":"1987","unstructured":"Rayward-Smith, V.J.: The Hamiltonian completion problem and its solution. Eng. Optim. 10(4), 309\u2013322 (1987). https:\/\/doi.org\/10.1080\/03052158708902546","journal-title":"Eng. Optim."},{"issue":"3","key":"9447_CR28","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(3), 623\u2013641 (1982). https:\/\/doi.org\/10.1145\/322326.322328","journal-title":"J. ACM"},{"issue":"2","key":"9447_CR29","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM 31(2), 245\u2013281 (1984). https:\/\/doi.org\/10.1145\/62.2160","journal-title":"J. ACM"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-020-09447-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-020-09447-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-020-09447-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T08:32:27Z","timestamp":1696321947000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-020-09447-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9447"],"URL":"https:\/\/doi.org\/10.1007\/s10732-020-09447-9","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,1]]},"assertion":[{"value":"26 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}