{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:20:34Z","timestamp":1759666834201},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf02253612","type":"journal-article","created":{"date-parts":[[2005,11,15]],"date-time":"2005-11-15T16:39:39Z","timestamp":1132072779000},"page":"191-211","source":"Crossref","is-referenced-by-count":10,"title":["Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood"],"prefix":"10.1007","volume":"54","author":[{"given":"R. E.","family":"Burkard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. G.","family":"Deineko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02253612_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1978","unstructured":"Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica2, 195\u2013208 (1978).","journal-title":"Algorithmica"},{"key":"BF02253612_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0255(82)90055-X","volume":"27","author":"K. V. S. Bhat","year":"1992","unstructured":"Bhat, K. V. S.: The optimum assignments and a new heuristic approach for the traveling salesman problem. Inform. Sciences27, 121\u2013132 (1992).","journal-title":"Inform. Sciences"},{"key":"BF02253612_CR3","first-page":"16","volume":"3","author":"V. Ya. Burdyuk","year":"1976","unstructured":"Burdyuk, V. Ya., Trofimov, V. N.: Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem (in Russian). Izv. Akad. Nauk SASS, Tech. Kibernet.3, 16\u201322 (1976) [Translation: Engineering Cybernetics14, 12\u201318 (1976)].","journal-title":"Izv. Akad. Nauk SASS, Tech. Kibernet"},{"key":"BF02253612_CR4","first-page":"245","volume":"24","author":"J. Carlier","year":"1990","unstructured":"Carlier, J., Villon, P.: A new heuristic for the travelling salesman problem. Recherche op\u00e9rationelle (RAIRO)24, 245\u2013253 (1990).","journal-title":"Recherche op\u00e9rationelle (RAIRO)"},{"key":"BF02253612_CR5","first-page":"47","volume":"14","author":"V. G. Deineko","year":"1979","unstructured":"Deineko, V. G.: Applying a dynamic programming to solving a special traveling salesmen problem (in Russian). Issledovanie operaziy i ASU, Kiev 14, 47\u201350 (1979).","journal-title":"Issledovanie operaziy i ASU, Kiev"},{"key":"BF02253612_CR6","unstructured":"Deineko, V. G., Filonenko, V. L.: On the reconstruction of specially structured matrices (in Russian). Aktualnye problemy EVMi programmirovanie, Dnepropetrovsk, DGU, 43\u201345 (1979)."},{"key":"BF02253612_CR7","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","volume":"11","author":"D. Eppstein","year":"1990","unstructured":"Eppstein, D.: Sequence comparison with mixed convex and concave costs. J. Algorithms11, 85\u2013101 (1990).","journal-title":"J. Algorithms"},{"key":"BF02253612_CR8","first-page":"128","volume":"4","author":"N. E. Gaikov","year":"1980","unstructured":"Gaikov, N. E.: On the minimization of linear form on cycles (in Russian). Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk4, 128 (1980).","journal-title":"Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk"},{"key":"BF02253612_CR9","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"P. C. Gilmore","year":"1964","unstructured":"Gilmore, P. C., Gomory, R. E.: Sequencing a one state variable machine: a solvable case of the travelling salesman problem. Oper. Res.12, 655\u2013679 (1964).","journal-title":"Oper. Res."},{"key":"BF02253612_CR10","first-page":"87","volume-title":"Well solved special cases","author":"P. C. Gilmore","year":"1985","unstructured":"Gilmore, P. C., Lawler, E. L., Shmoys, D. B.: Well solved special cases. Chapter 4 in [13]."},{"key":"BF02253612_CR11","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/0208045","volume":"8","author":"R. M. Karp","year":"1979","unstructured":"Karp, R. M.: A patching algorithm for nonsymmetric traveling salesman problem. SIAM J. Comput.8, 561\u2013573 (1979).","journal-title":"SIAM J. Comput."},{"key":"BF02253612_CR12","unstructured":"Klyaus, P. S.: Generation of test problems for the traveling salesman problem (in Russian), unpublished manuscript [Preprint No. 16, Inst. Mat. AN BSSR, Minsk], (1976)."},{"key":"BF02253612_CR13","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. Chichester: Wiley, 1985."},{"key":"BF02253612_CR14","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(91)90118-2","volume":"40","author":"J. K. Park","year":"1991","unstructured":"Park, J. K.: A special case of then-vertex traveling salesman problem that can be solved inO(n) time. Inform. Process. Lett.40, 247\u2013254 (1991).","journal-title":"Inform. Process. Lett."},{"key":"BF02253612_CR15","volume-title":"On quadratic choice problems","author":"V. I. Sarvanov","year":"1978","unstructured":"Sarvanov, V. I.: On quadratic choice problems (in Russian). Ph.D. Thesis, Inst. Mat. AN BSSR, Minsk (1978)."},{"key":"BF02253612_CR16","first-page":"533","volume":"253","author":"V. I. Sarvanov","year":"1980","unstructured":"Sarvanov, V. I.: On the complexity of minimizing a linear form on a set of cyclic permutations (in Russian). Dokl. AN SSSR253, 533\u2013535 (1980) [Translation: Soviet Math. Dokl. 22, 118\u2013120].","journal-title":"Dokl. AN SSSR"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02253612.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02253612\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02253612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T14:52:27Z","timestamp":1558018347000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02253612"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF02253612"],"URL":"https:\/\/doi.org\/10.1007\/bf02253612","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}