{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:41:06Z","timestamp":1725475266364},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540340751"},{"type":"electronic","value":"9783540340768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11751595_84","type":"book-chapter","created":{"date-parts":[[2006,5,11]],"date-time":"2006-05-11T14:27:59Z","timestamp":1147357679000},"page":"793-801","source":"Crossref","is-referenced-by-count":1,"title":["One-Sided Monge TSP Is NP-Hard"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Deineko","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Tiskin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"84_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"R.K. Ahuja","year":"2002","unstructured":"Ahuja, R.K., Ergun, \u00d6., Orlin, J.B., Punnen, A.: A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics\u00a0123, 75\u2013102 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"84_CR2","unstructured":"Arkin, E.M., Bemder, M.A., Demaine, E., Fekete, S.P., Mitchell, J.S., Sthia, S.: Optimal covering tours with turn costs. In: Proc. 13th ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 138\u2013147 (2001)"},{"issue":"3","key":"84_CR3","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S0036144596297514","volume":"40","author":"R.E. Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the TSP: A survey. SIAM Review\u00a040(3), 496\u2013546 (1998)","journal-title":"SIAM Review"},{"key":"84_CR4","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0020-0190(98)00119-7","volume":"67","author":"R.E. Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G.: On the traveling salesman problem with a relaxed Monge matrix. Information Processing Letters\u00a067, 231\u2013237 (1998)","journal-title":"Information Processing Letters"},{"key":"84_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics\u00a070, 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"84_CR6","doi-asserted-by":"crossref","unstructured":"Deineko, V.G., Klinz, B., Woeginger, G.J.: Four point conditions for symmetric TSP and exponential neighbourhoods. In: Proc. 17th ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 544\u2013553 (2006)","DOI":"10.1145\/1109557.1109617"},{"key":"84_CR7","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"V.G. Deineko","year":"2000","unstructured":"Deineko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Mathematical Programming\u00a087, 519\u2013542 (2000)","journal-title":"Mathematical Programming"},{"key":"84_CR8","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/S0166-218X(99)00148-1","volume":"99","author":"V.G. Deineko","year":"2000","unstructured":"Deineko, V.G., Woeginger, G.J.: The maximum travelling salesman problem on symmetric Demidenko matrices. Discrete Applied Mathematics\u00a099, 413\u2013425 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"84_CR9","first-page":"28","volume":"5","author":"V.M. Demidenko","year":"1976","unstructured":"Demidenko, V.M.: A special case of traveling salesman problems. Izv. Akad. Nauk. BSSR, Ser. Fiz.-mat. Nauk\u00a05, 28\u201332 (1976) (in Russian)","journal-title":"Izv. Akad. Nauk. BSSR, Ser. Fiz.-mat. Nauk"},{"key":"84_CR10","volume-title":"Computers and intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman and Co., San Francisco (1979)"},{"key":"84_CR11","unstructured":"Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. Ch.\u00a07. In [17], pp. 207\u2013249 (1985)"},{"volume-title":"The travelling salesman problem and its variations","year":"2002","key":"84_CR12","unstructured":"Gutin, G., Punnen, A.P. (eds.): The travelling salesman problem and its variations. Kluwer Academic Publishers, Dordrecht (2002)"},{"issue":"4","key":"84_CR13","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"Itai, A., Papadimitiou, C.H., Szwarcfiter, J.L.: Hamiltonian paths in grid graphs. SIAM Journal on Computing\u00a011(4), 676\u2013686 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"84_CR14","doi-asserted-by":"crossref","unstructured":"Kabadi, S.N.: Polynomially solvable cases of the TSP. Ch.\u00a011. In [12], pp. 489\u2013583 (2002)","DOI":"10.1007\/0-306-48213-4_11"},{"key":"84_CR15","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.4153\/CJM-1975-104-6","volume":"27","author":"K. Kalmanson","year":"1975","unstructured":"Kalmanson, K.: Edgeconvex circuits and the traveling salesman problem. Canadian Journal of Mathematics\u00a027, 1000\u20131010 (1975)","journal-title":"Canadian Journal of Mathematics"},{"key":"84_CR16","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF01584089","volume":"1","author":"E.L. Lawler","year":"1971","unstructured":"Lawler, E.L.: A solvable case of the traveling salesman problem. Mathematical Programming\u00a01, 267\u2013269 (1971)","journal-title":"Mathematical Programming"},{"key":"84_CR17","volume-title":"The Traveling Salesman Problem","author":"E.L. Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem. Wiley, Chichester (1985)"},{"key":"84_CR18","unstructured":"Lenhart, W., Umans, U.: Hamiltonian cycles in solid grid graphs. In: Proceedings of 38 Annual Symposium on Foundations of Computer Science, FOCS 1997, pp. 496\u2013596 (1997)"},{"key":"84_CR19","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1090\/S0002-9939-1964-0163216-6","volume":"15","author":"L.V. Quintas","year":"1964","unstructured":"Quintas, L.V., Supnick, F.: Extreme Hamiltonian Circuits: Resolution of the convex-odd case. Proc. Amer. Math. Soc.\u00a015, 454\u2013459 (1964)","journal-title":"Proc. Amer. Math. Soc."},{"key":"84_CR20","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1090\/S0002-9939-1965-0185508-8","volume":"16","author":"L.V. Quintas","year":"1965","unstructured":"Quintas, L.V., Supnick, F.: Extreme Hamiltonian Circuits: Resolution of the convex-even case. Proc. Amer. Math. Soc.\u00a016, 1058\u20131061 (1965)","journal-title":"Proc. Amer. Math. Soc."},{"key":"84_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.2307\/1970124","volume":"66","author":"F. Supnick","year":"1957","unstructured":"Supnick, F.: Extreme Hamiltonian lines. Annals of Math.\u00a066, 179\u2013201 (1957)","journal-title":"Annals of Math."},{"key":"84_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2004.06.014","volume":"146","author":"G. Steiner","year":"2005","unstructured":"Steiner, G., Xue, X.: The maximum traveling salesman problem on van der Veen matrices. Discrete Applied Mathematics\u00a0146, 1\u20132 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"84_CR23","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1137\/S0895480190191619","volume":"7","author":"J.A.A. Veen van der","year":"1994","unstructured":"van der Veen, J.A.A.: A new class of pyramidally solvable symmetric traveling salesman problems. SIAM J. Discr. Math.\u00a07, 585\u2013592 (1994)","journal-title":"SIAM J. Discr. Math."},{"key":"84_CR24","first-page":"34","volume":"1","author":"Y.M. Volodarskiy","year":"1976","unstructured":"Volodarskiy, Y.M., Gabovich, E.Y., Zacharin, A.Y.: A solvable case in discrete programming. Izv. Akad. Nauk. SSSR, Ser. Techn. Kibernetika\u00a01, 34\u201344 (1976) (in Russian); English translation in Engineering Cybernetics 14, 23\u201332 (1977)","journal-title":"Izv. Akad. Nauk. SSSR, Ser. Techn. Kibernetika"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications - ICCSA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11751595_84.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:00:18Z","timestamp":1619506818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11751595_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540340751","9783540340768"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11751595_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}