{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:20:35Z","timestamp":1765232435562,"version":"3.41.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,2,24]],"date-time":"2017-02-24T00:00:00Z","timestamp":1487894400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s10878-017-0119-z","type":"journal-article","created":{"date-parts":[[2017,2,24]],"date-time":"2017-02-24T13:50:22Z","timestamp":1487944222000},"page":"891-915","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["The traveling salesman problem on grids with forbidden neighborhoods"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2812-043X","authenticated-orcid":false,"given":"Anja","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Hungerl\u00e4nder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,24]]},"reference":[{"key":"119_CR1","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The traveling salesman problem: a computational study (Princeton series in applied mathematics). Princeton University Press, Princeton. ISBN 0691129932"},{"issue":"2","key":"119_CR2","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1137\/S0097539797320281","volume":"29","author":"EM Arkin","year":"1999","unstructured":"Arkin EM, Chiang Y-J, Mitchell JSB, Skiena SS, Yang T-C (1999) On the maximum scatter traveling salesperson problem. SIAM J Comput 29(2):515\u2013544","journal-title":"SIAM J Comput"},{"issue":"3","key":"119_CR3","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/S0097539703434267","volume":"35","author":"E Arkin","year":"2005","unstructured":"Arkin E, Bender M, Demaine E, Fekete S, Mitchell J, Sethia S (2005) Optimal covering tours with turn costs. SIAM J Comput 35(3):531\u2013566","journal-title":"SIAM J Comput"},{"issue":"6\u20137","key":"119_CR4","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1016\/j.comgeo.2008.11.004","volume":"42","author":"EM Arkin","year":"2009","unstructured":"Arkin EM, Fekete SP, Islam K, Meijer H, Mitchell JS, N\u00fa\u00f1ez-Rodr\u00edguez Y, Polishchuk V, Rappaport D, Xiao H (2009) Not being (super)thin or solid is hard: a study of grid hamiltonicity. Comput Geom 42(6\u20137):582\u2013605","journal-title":"Comput Geom"},{"issue":"5","key":"119_CR5","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753\u2013782","journal-title":"J ACM"},{"issue":"3","key":"119_CR6","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501\u2013555","journal-title":"J ACM"},{"issue":"4","key":"119_CR7","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-004-1124-z","volume":"41","author":"Y-J Chiang","year":"2004","unstructured":"Chiang Y-J (2004) New approximation results for the maximum scatter TSP. Algorithmica 41(4):309\u2013341. doi: 10.1007\/s00453-004-1124-z","journal-title":"Algorithmica"},{"key":"119_CR8","unstructured":"Christofides, N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, GSIA, Carnegie-Mellon University,"},{"issue":"2","key":"119_CR9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0166-218X(92)00170-Q","volume":"50","author":"A Conrad","year":"1994","unstructured":"Conrad A, Hindrichs T, Morsy H, Wegener I (1994) Solution of the knight\u2019s Hamiltonian path problem on chessboards. Discret Appl Math 50(2):125\u2013134","journal-title":"Discret Appl Math"},{"key":"119_CR10","doi-asserted-by":"crossref","DOI":"10.1515\/9781400841103","volume-title":"In pursuit of the traveling salesman: mathematics at the limits of computation","author":"WJ Cook","year":"2011","unstructured":"Cook WJ (2011) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton"},{"key":"119_CR11","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1080\/00150517.1978.12430328","volume":"16","author":"P Cull","year":"1978","unstructured":"Cull P, De Curtins J (1978) Knight\u2019s tour revisited. Fibonacci Q 16:276\u2013285","journal-title":"Fibonacci Q"},{"key":"119_CR12","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper Res 2:393\u2013410","journal-title":"Oper Res"},{"key":"119_CR13","unstructured":"Demaine E, Mitchell JSB, O\u2019Rourke J (2004) The open problems project. http:\/\/cs.smith.edu\/~jorourke\/TOPP\/"},{"key":"119_CR14","first-page":"310","volume":"15","author":"L Euler","year":"1759","unstructured":"Euler L (1759) Solution d\u2019une question curieuse que ne paroit soumise\u00e0 aucune analyse. Mem Acad Dessciences Berl 15:310\u2013337","journal-title":"Mem Acad Dessciences Berl"},{"key":"119_CR15","doi-asserted-by":"crossref","unstructured":"Garey MR, Graham RL, Johnson DS (1976) Some NP-complete geometric problems. In: Proceedings of the eighth annual ACM symposium on theory of computing, STOC \u201976, pp 10\u201322, New York, NY, USA. ACM","DOI":"10.1145\/800113.803626"},{"key":"119_CR16","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2002","unstructured":"Gutin G, Punnen A (2002) The traveling salesman problem and its variations. Springer, Berlin"},{"key":"119_CR17","unstructured":"Hoffmann I, Kurz S, Rambau J (2015) The maximum scatter TSP on a regular grid. https:\/\/epub.uni-bayreuth.de\/2524\/"},{"issue":"4","key":"119_CR18","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai A, Papadimitriou C, Szwarcfiter J (1982) Hamilton paths in grid graphs. SIAM J Comput 11(4):676\u2013686","journal-title":"SIAM J Comput"},{"key":"119_CR19","unstructured":"Jellen A, Fischer A, Hungerl\u00e4nder P (2016) Implementation of algorithms and illustration of optimal tours for the TSPFN with $$r \\in \\{0,1,\\sqrt{2} \\}$$ r \u2208 { 0 , 1 , 2 } . http:\/\/philipphungerlaender.jimdo.com\/tspfn-code\/"},{"key":"119_CR20","unstructured":"Korda\u00df R (2014) Untersuchungen zum Eigenspannungs- und Verzugsverhalten beim Laserstrahlschmelzen. Masterarbeit, Technische Universit\u00e4t Chemnitz, Fakult\u00e4t f\u00fcr Maschinenbau, Professur f\u00fcr Werkzeugmaschinen und Umformtechnik"},{"key":"119_CR21","unstructured":"Kozma L, M\u00f6mke T (2015) A PTAS for Euclidean maximum scatter TSP. CoRR, arXiv:1512.02963"},{"key":"119_CR22","doi-asserted-by":"publisher","unstructured":"Kozma L, M\u00f6mke T (2017) Maximum scatter TSP in doubling metrics, pp 143\u2013153. doi: 10.1137\/1.9781611974782.10","DOI":"10.1137\/1.9781611974782.10"},{"issue":"3","key":"119_CR23","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.dam.2004.11.002","volume":"146","author":"S-S Lin","year":"2005","unstructured":"Lin S-S, Wei C-L (2005) Optimal algorithms for constructing knight\u2019s tours on arbitrary chessboards. Discret Appl Math 146(3):219\u2013232","journal-title":"Discret Appl Math"},{"key":"119_CR24","unstructured":"MATLAB. version 7.10.0 (r2010a) (2010)"},{"issue":"3","key":"119_CR25","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237\u2013244","journal-title":"Theor Comput Sci"},{"issue":"3","key":"119_CR26","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0166-218X(96)00010-8","volume":"73","author":"I Parberry","year":"1997","unstructured":"Parberry I (1997) An efficient algorithm for the knight\u2019s tour problem. Discret Appl Math 73(3):251\u2013260","journal-title":"Discret Appl Math"},{"key":"119_CR27","volume-title":"The traveling salesman: computational solutions for TSP applications","author":"G Reinelt","year":"1994","unstructured":"Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Springer, Berlin"},{"issue":"5","key":"119_CR28","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/2690649","volume":"64","author":"AJ Schwenk","year":"1991","unstructured":"Schwenk AJ (1991) Which rectangular chessboards have a knight\u2019s tour? Math Mag 64(5):325\u2013332","journal-title":"Math Mag"},{"key":"119_CR29","doi-asserted-by":"crossref","unstructured":"Umans C., Lenhart W (1997) Hamiltonian cycles in solid grid graphs. In: 38th annual symposium on foundations of computer science, pp 496\u2013505","DOI":"10.1109\/SFCS.1997.646138"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0119-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0119-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0119-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T18:16:00Z","timestamp":1750011360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0119-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,24]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["119"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0119-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,2,24]]}}}