{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:07:23Z","timestamp":1773655643730,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030226282","type":"print"},{"value":"9783030226299","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-22629-9_26","type":"book-chapter","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:02:42Z","timestamp":1560283362000},"page":"374-389","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Simulated Annealing Approach to Verify Vertex Adjacencies in the Traveling Salesperson Polytope"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6280-3325","authenticated-orcid":false,"given":"Anna","family":"Kozlova","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4705-2409","authenticated-orcid":false,"given":"Andrei","family":"Nikolaev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-540-77918-6_9","volume-title":"Approximation and Online Algorithms","author":"AA Ageev","year":"2008","unstructured":"Ageev, A.A., Pyatkin, A.V.: A 2-approximation algorithm for the metric 2-peripatetic salesman problem. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol. 4927, pp. 103\u2013115. Springer, Heidelberg (2008). \n                      https:\/\/doi.org\/10.1007\/978-3-540-77918-6_9"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.dam.2016.10.024","volume":"218","author":"NE Aguilera","year":"2017","unstructured":"Aguilera, N.E., Katz, R.D., Tolomei, P.B.: Vertex adjacencies in the set covering polyhedron. Discrete Appl. Math. 218, 40\u201356 (2017). \n                      https:\/\/doi.org\/10.1016\/j.dam.2016.10.024","journal-title":"Discrete Appl. Math."},{"issue":"14","key":"26_CR3","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1016\/j.disc.2005.11.030","volume":"306","author":"TS Arthanari","year":"2006","unstructured":"Arthanari, T.S.: On pedigree polytopes and Hamiltonian cycles. Discrete Math. 306(14), 1474\u20131492 (2006). \n                      https:\/\/doi.org\/10.1016\/j.disc.2005.11.030","journal-title":"Discrete Math."},{"issue":"3","key":"26_CR4","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/opre.33.3.527","volume":"33","author":"ML Balinski","year":"1985","unstructured":"Balinski, M.L.: Signature methods for the assignment problem. Oper. Res. 33(3), 527\u2013536 (1985). \n                      https:\/\/doi.org\/10.1287\/opre.33.3.527","journal-title":"Oper. Res."},{"issue":"9","key":"26_CR5","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1016\/j.dam.2008.06.025","volume":"157","author":"A.E. Baburin","year":"2009","unstructured":"Baburin, A.E., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.Th.: Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157, 1988\u20131992 (2009). \n                      https:\/\/doi.org\/10.1016\/j.dam.2008.06.025","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR6","first-page":"1137","volume":"44","author":"VA Bondarenko","year":"1983","unstructured":"Bondarenko, V.A.: Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms. Autom. Rem. Contr. 44, 1137\u20131142 (1983)","journal-title":"Autom. Rem. Contr."},{"key":"26_CR7","unstructured":"Bondarenko, V.A., Maksimenko, A.N.: Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoy optimizatsii (Geometric constructions and complexity in combinatorial optimization), LKI, Moscow (2008). (in Russian)"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2016\/7863650","volume":"2016","author":"Vladimir Bondarenko","year":"2016","unstructured":"Bondarenko, V.A., Nikolaev, A.V.: On graphs of the cone decompositions for the min-cut and max-cut problems. Int. J. Math. Sci. 2016 (2016). Article ID 7863650, 6 p. \n                      https:\/\/doi.org\/10.1155\/2016\/7863650","journal-title":"International Journal of Mathematics and Mathematical Sciences"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.endm.2017.06.030","volume":"61","author":"VA Bondarenko","year":"2017","unstructured":"Bondarenko, V.A., Nikolaev, A.V.: Some properties of the skeleton of the pyramidal tours polytope. Electron. Notes Discrete Math. 61, 131\u2013137 (2017). \n                      https:\/\/doi.org\/10.1016\/j.endm.2017.06.030","journal-title":"Electron. Notes Discrete Math."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1134\/S1990478918010027","volume":"12","author":"VA Bondarenko","year":"2018","unstructured":"Bondarenko, V.A., Nikolaev, A.V.: On the skeleton of the polytope of pyramidal tours. J. Appl. Ind. Math. 12, 9\u201318 (2018). \n                      https:\/\/doi.org\/10.1134\/S1990478918010027","journal-title":"J. Appl. Ind. Math."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(87)90017-5","volume":"18","author":"CR Chegireddy","year":"1987","unstructured":"Chegireddy, C.R., Hamacher, H.W.: Algorithms for finding K-best perfect matchings. Discrete Appl. Math. 18, 155\u2013165 (1987). \n                      https:\/\/doi.org\/10.1016\/0166-218X(87)90017-5","journal-title":"Discrete Appl. Math."},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0218195901000560","volume":"11","author":"T Christof","year":"2001","unstructured":"Christof, T., Reinelt, G.: Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes. Int. J. Comput. Geom. Appl. 11, 423\u2013437 (2001). \n                      https:\/\/doi.org\/10.1142\/S0218195901000560","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.fss.2009.05.004","volume":"161","author":"EF Combarro","year":"2010","unstructured":"Combarro, E.F., Miranda, P.: Adjacency on the order polytope with applications to the theory of fuzzy measures. Fuzzy Set. Syst. 161, 619\u2013641 (2010). \n                      https:\/\/doi.org\/10.1016\/j.fss.2009.05.004","journal-title":"Fuzzy Set. Syst."},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1080\/02331939208843770","volume":"23","author":"JBJM Kort De","year":"1992","unstructured":"De Kort, J.B.J.M.: Bounds for the symmetric 2-peripatetic salesman problem. Optim. 23, 357\u2013367 (1992). \n                      https:\/\/doi.org\/10.1080\/02331939208843770","journal-title":"Optim."},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965). \n                      https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"issue":"2","key":"26_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2716307","volume":"62","author":"Samuel Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62 (2015). Article No. 17. \n                      https:\/\/doi.org\/10.1145\/2716307","journal-title":"Journal of the ACM"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1137\/0206011","volume":"6","author":"HN Gabow","year":"1977","unstructured":"Gabow, H.N.: Two algorithms for generating weighted spanning trees in order. SIAM J. Comput. 6, 139\u2013150 (1977). \n                      https:\/\/doi.org\/10.1137\/0206011","journal-title":"SIAM J. Comput."},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1134\/S1990478912010085","volume":"6","author":"AN Glebov","year":"2012","unstructured":"Glebov, A.N., Zambalaeva, D.Z.: A polynomial algorithm with approximation ratio 7\/9 for the maximum two peripatetic salesmen problem. J. Appl. Ind. Math. 6, 69\u201389 (2012). \n                      https:\/\/doi.org\/10.1134\/S1990478912010085","journal-title":"J. Appl. Ind. Math."},{"key":"26_CR19","first-page":"251","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., Padberg, M.: Polyhedral theory. In: Lawler, E., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 251\u2013305. Wiley, Chichester (1985)"},{"issue":"4","key":"26_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An \n                      \n                        \n                      \n                      $$n^{5\/2}$$\n                     algorithm for maximum matchings in bipartite graphs. SIAM J. Comp. 2(4), 225\u2013231 (1973). \n                      https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comp."},{"issue":"4598","key":"26_CR21","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983). \n                      https:\/\/doi.org\/10.1126\/science.220.4598.671","journal-title":"Science"},{"key":"26_CR22","first-page":"51","volume":"10","author":"AP Kozlova","year":"2018","unstructured":"Kozlova, A.P., Nikolaev, A.V.: Proverka smezhnosti vershin mnogogrannika zadachi kommivoyazhyora (Verification of vertex adjacency in the traveling salesperson polytope). Zametki po informatike i matematike (Notes on Computer Science and Mathematics) 10, 51\u201358 (2018). (in Russian)","journal-title":"Zametki po informatike i matematike (Notes on Computer Science and Mathematics)"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.aim.2013.01.005","volume":"237","author":"D K\u00fchn","year":"2013","unstructured":"K\u00fchn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of Kelly\u2019s conjecture for large tournaments. Adv. Math. 237, 62\u2013146 (2013). \n                      https:\/\/doi.org\/10.1016\/j.aim.2013.01.005","journal-title":"Adv. Math."},{"key":"26_CR24","doi-asserted-by":"publisher","unstructured":"Micali, S., Vazirani, V.V.: An \n                      \n                        \n                      \n                      $$O({\\sqrt{|V|}}\\cdot |E|)$$\n                     algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, pp. 17\u201327 (1980). \n                      https:\/\/doi.org\/10.1109\/SFCS.1980.12","DOI":"10.1109\/SFCS.1980.12"},{"issue":"1","key":"26_CR25","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF01585502","volume":"7","author":"MW Padberg","year":"1974","unstructured":"Padberg, M.W., Rao, M.R.: The travelling salesman problem and a class of polyhedra of diameter two. Math. Program. 7(1), 32\u201345 (1974). \n                      https:\/\/doi.org\/10.1007\/BF01585502","journal-title":"Math. Program."},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01588973","volume":"14","author":"CH Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-Complete. Math. Program. 14, 312\u2013324 (1978). \n                      https:\/\/doi.org\/10.1007\/BF01588973","journal-title":"Math. Program."},{"key":"26_CR27","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0130021","volume":"30","author":"MR Rao","year":"1976","unstructured":"Rao, M.R.: Adjacency of the traveling salesman tours and 0-1 vertices. SIAM J. Appl. Math. 30, 191\u2013198 (1976). \n                      https:\/\/doi.org\/10.1137\/0130021","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"26_CR28","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0895480196312462","volume":"11","author":"FJ Rispoli","year":"1998","unstructured":"Rispoli, F.J., Cosares, S.: A bound of \n                      \n                        \n                      \n                      $$4$$\n                     for the diameter of the symmetric traveling salesman polytope. SIAM J. Discrete Math. 11(3), 373\u2013380 (1998). \n                      https:\/\/doi.org\/10.1137\/S0895480196312462","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(93)90169-O","volume":"43","author":"G Sierksma","year":"1993","unstructured":"Sierksma, G.: The skeleton of the symmetric traveling salesman polytope. Discrete Appl. Math. 43, 63\u201374 (1993). \n                      https:\/\/doi.org\/10.1016\/0166-218X(93)90169-O","journal-title":"Discrete Appl. Math."},{"key":"26_CR30","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954). \n                      https:\/\/doi.org\/10.4153\/CJM-1954-033-3","journal-title":"Can. J. Math."}],"container-title":["Lecture Notes in Computer Science","Mathematical Optimization Theory and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22629-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:04:41Z","timestamp":1560283481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-22629-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030226282","9783030226299"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22629-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"MOTOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Mathematical Optimization Theory and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"motor2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/motor2019.uran.ru","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}