{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:48:51Z","timestamp":1767016131225,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"european research council","doi-asserted-by":"publisher","award":["71971167"],"award-info":[{"award-number":["71971167"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72192830","72192834"],"award-info":[{"award-number":["72192830","72192834"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["202206280182"],"award-info":[{"award-number":["202206280182"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s10878-023-01104-8","type":"journal-article","created":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T20:02:32Z","timestamp":1707768152000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem"],"prefix":"10.1007","volume":"47","author":[{"given":"Jun","family":"Wu","sequence":"first","affiliation":[]},{"given":"Zhen","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Guiqing","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Yongxi","family":"Cheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"issue":"1","key":"1104_CR1","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s11590-010-0252-4","volume":"6","author":"J Bae","year":"2012","unstructured":"Bae J, Rathinam S (2012) Approximation algorithms for multiple terminal, Hamiltonian path problems. Optim Lett 6(1):69\u201385","journal-title":"Optim Lett"},{"key":"1104_CR2","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh"},{"issue":"502","key":"1104_CR3","first-page":"67","volume":"173","author":"R Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory. Math Gaz 173(502):67\u2013128","journal-title":"Math Gaz"},{"issue":"1","key":"1104_CR4","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0196-6774(84)90042-7","volume":"5","author":"HN Gabow","year":"1984","unstructured":"Gabow HN, Tarjan RE (1984) Efficient algorithms for a family of matroid intersection problems. J Algorithms 5(1):80\u2013131","journal-title":"J Algorithms"},{"key":"1104_CR5","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.cie.2017.06.022","volume":"111","author":"A Giannakos","year":"2017","unstructured":"Giannakos A, Hifi M, Kheffache R, Ouafi R (2017) An approximation algorithm for the $$k$$-fixed depots problem. Comput Ind Eng 111:50\u201355","journal-title":"Comput Ind Eng"},{"issue":"5","key":"1104_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"JA Hoogeveen","year":"1991","unstructured":"Hoogeveen JA (1991) Analysis of Christofides heuristic: some paths are more difficult than cycles. Oper Res Lett 10(5):291\u2013295","journal-title":"Oper Res Lett"},{"issue":"6","key":"1104_CR7","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.orl.2007.02.001","volume":"35","author":"W Malik","year":"2007","unstructured":"Malik W, Rathinam S, Darbha S (2007) An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Oper Res Lett 35(6):747\u2013753","journal-title":"Oper Res Lett"},{"issue":"1","key":"1104_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.orl.2009.10.001","volume":"38","author":"S Rathinam","year":"2010","unstructured":"Rathinam S, Sengupta R (2010) 3\/2-approximation algorithm for two variants of a 2-depot Hamiltonian path problem. Oper Res Lett 38(1):63\u201368","journal-title":"Oper Res Lett"},{"issue":"1","key":"1104_CR9","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TASE.2006.872110","volume":"4","author":"S Rathinam","year":"2007","unstructured":"Rathinam S, Sengupta R, Darbha S (2007) A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans Autom Sci Eng 4(1):98\u2013104","journal-title":"IEEE Trans Autom Sci Eng"},{"issue":"4","key":"1104_CR10","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1287\/ijoc.2015.0650","volume":"27","author":"Z Xu","year":"2015","unstructured":"Xu Z, Rodrigues B (2015) A 3\/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS J Comput 27(4):636\u2013645","journal-title":"INFORMS J Comput"},{"key":"1104_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2019.05.002","volume":"34","author":"Y Yang","year":"2019","unstructured":"Yang Y, Liu Z (2019) Approximating the multiple-depot multiple-terminal Hamiltonian path problem. Discrete Optim 34:100545","journal-title":"Discrete Optim"},{"issue":"4","key":"1104_CR12","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1007\/s11590-021-01774-5","volume":"16","author":"Y Yang","year":"2022","unstructured":"Yang Y, Liu Z, Yu W (2022) Approximation algorithms for the $$k$$-depots Hamiltonian path problem. Optim Lett 16(4):1215\u20131234","journal-title":"Optim Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01104-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-023-01104-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-023-01104-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T23:13:49Z","timestamp":1710285229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-023-01104-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1104"],"URL":"https:\/\/doi.org\/10.1007\/s10878-023-01104-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,2,12]]},"assertion":[{"value":"26 December 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}}],"article-number":"7"}}