{"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":1773655643980,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100011051","name":"Council on grants of the President of the Russian Federation","doi-asserted-by":"publisher","award":["MK-2620.2018.1"],"award-info":[{"award-number":["MK-2620.2018.1"]}],"id":[{"id":"10.13039\/501100011051","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":[[2021,8]]},"DOI":"10.1007\/s10878-020-00652-7","type":"journal-article","created":{"date-parts":[[2020,9,29]],"date-time":"2020-09-29T23:44:14Z","timestamp":1601423054000},"page":"212-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4705-2409","authenticated-orcid":false,"given":"Andrei","family":"Nikolaev","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6280-3325","authenticated-orcid":false,"given":"Anna","family":"Kozlova","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"key":"652_CR1","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.dam.2016.10.024","volume":"218","author":"NE Aguilera","year":"2017","unstructured":"Aguilera NE, Katz RD, Tolomei PB (2017) Vertex adjacencies in the set covering polyhedron. Discrete Appl Math 218:40\u201356. https:\/\/doi.org\/10.1016\/j.dam.2016.10.024","journal-title":"Discrete Appl Math"},{"key":"652_CR2","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1016\/j.disc.2005.11.030","volume":"306","author":"TS Arthanari","year":"2006","unstructured":"Arthanari TS (2006) On pedigree polytopes and Hamiltonian cycles. Discrete Math 306:1474\u20131492. https:\/\/doi.org\/10.1016\/j.disc.2005.11.030","journal-title":"Discrete Math"},{"key":"652_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.disopt.2013.07.001","volume":"10","author":"TS Arthanari","year":"2013","unstructured":"Arthanari TS (2013) Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope. Discrete Optim 10:224\u2013232. https:\/\/doi.org\/10.1016\/j.disopt.2013.07.001","journal-title":"Discrete Optim"},{"key":"652_CR4","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.1109\/TC.2003.1234525","volume":"52","author":"MM Bae","year":"2003","unstructured":"Bae MM, Bose B (2003) Edge disjoint Hamiltonian cycles in $$k$$-ary $$n$$-cubes and hypercubes. IEEE Trans Comput 52:1271\u20131284. https:\/\/doi.org\/10.1109\/TC.2003.1234525","journal-title":"IEEE Trans Comput"},{"key":"652_CR5","doi-asserted-by":"publisher","first-page":"4253","DOI":"10.1016\/j.disc.2008.12.027","volume":"309","author":"RF Bailey","year":"2009","unstructured":"Bailey RF (2009) Error-correcting codes from permutation groups. Discrete Math 309:4253\u20134265. https:\/\/doi.org\/10.1016\/j.disc.2008.12.027","journal-title":"Discrete Math"},{"key":"652_CR6","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/opre.33.3.527","volume":"33","author":"ML Balinski","year":"1985","unstructured":"Balinski ML (1985) Signature methods for the assignment problem. Oper Res 33:527\u2013536. https:\/\/doi.org\/10.1287\/opre.33.3.527","journal-title":"Oper Res"},{"key":"652_CR7","first-page":"1137","volume":"44","author":"VA Bondarenko","year":"1983","unstructured":"Bondarenko VA (1983) Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms. Autom Rem Contr 44:1137\u20131142","journal-title":"Autom Rem Contr"},{"key":"652_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1134\/S1990478918010027","volume":"12","author":"VA Bondarenko","year":"2018","unstructured":"Bondarenko VA, Nikolaev AV (2018) On the skeleton of the polytope of pyramidal tours. J Appl Ind Math 12:9\u201318. https:\/\/doi.org\/10.1134\/S1990478918010027","journal-title":"J Appl Ind Math"},{"key":"652_CR9","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1134\/S1064562413050062","volume":"88","author":"VA Bondarenko","year":"2013","unstructured":"Bondarenko VA, Nikolaev AV (2013) Combinatorial and geometric properties of the Max-Cut and Min-Cut problems. Dokl Math 88:516\u2013517. https:\/\/doi.org\/10.1134\/S1064562413050062","journal-title":"Dokl Math"},{"key":"652_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/772862.772867","volume":"4","author":"C Clifton","year":"2002","unstructured":"Clifton C, Kantarcioglu M, Vaidya J, Lin X, Zhu MY (2002) Tools for privacy preserving distributed data mining. SIGKDD Explor Newsl 4:28\u201334. https:\/\/doi.org\/10.1145\/772862.772867","journal-title":"SIGKDD Explor Newsl"},{"key":"652_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 CR, Hamacher HW (1987) Algorithms for finding $$k$$-best perfect matchings. Discrete Appl Math 18:155\u2013165. https:\/\/doi.org\/10.1016\/0166-218X(87)90017-5","journal-title":"Discrete Appl Math"},{"key":"652_CR12","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.fss.2009.05.004","volume":"161","author":"EF Combarro","year":"2010","unstructured":"Combarro EF, Miranda P (2010) Adjacency on the order polytope with applications to the theory of fuzzy measures. Fuzzy Set Syst 161:619\u2013641. https:\/\/doi.org\/10.1016\/j.fss.2009.05.004","journal-title":"Fuzzy Set Syst"},{"key":"652_CR13","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-07124-4_9","volume-title":"Handbook of heuristics","author":"A Duarte","year":"2018","unstructured":"Duarte A, S\u00e1nchez-Oro J, Mladenovi\u0107 N, Todosijevi\u0107 R (2018) Variable neighborhood descent. In: Mart\u00ed R, Pardalos P, Resende M (eds) Handbook of heuristics. Springer, Cham, pp 341\u2013367. https:\/\/doi.org\/10.1007\/978-3-319-07124-4_9"},{"key":"652_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1137\/0206011","volume":"6","author":"HN Gabow","year":"1977","unstructured":"Gabow HN (1977) Two algorithms for generating weighted spanning trees in order. SIAM J Comput 6:139\u2013150. https:\/\/doi.org\/10.1137\/0206011","journal-title":"SIAM J Comput"},{"key":"652_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s11856-017-1583-y","volume":"222","author":"R Glebov","year":"2017","unstructured":"Glebov R, Luria Z, Sudakov B (2017) The number of Hamiltonian decompositions of regular graphs. Isr J Math 222:91\u2013108. https:\/\/doi.org\/10.1007\/s11856-017-1583-y","journal-title":"Isr J Math"},{"key":"652_CR16","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 (1985) Polyhedral theory. In: Lawler E, Lenstra JK, Rinnooy Kan A, Shmoys D (eds) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, Chichester, pp 251\u2013305"},{"key":"652_CR17","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/978-3-319-07124-4_19","volume-title":"Handbook of heuristics","author":"P Hansen","year":"2018","unstructured":"Hansen P, Mladenovi\u0107 N (2018) Variable neighborhood search. In: Mart\u00ed R, Pardalos P, Resende M (eds) Handbook of heuristics. Springer, Cham, pp 759\u2013787. https:\/\/doi.org\/10.1007\/978-3-319-07124-4_19"},{"key":"652_CR18","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s13675-016-0075-x","volume":"5","author":"P Hansen","year":"2017","unstructured":"Hansen P, Mladenovi\u0107 N, Todosijevi\u0107 R, Hanafi S (2017) Variable neighborhood search: basics and variants. Euro J Comput Optim 5:423\u2013454. https:\/\/doi.org\/10.1007\/s13675-016-0075-x","journal-title":"Euro J Comput Optim"},{"key":"652_CR19","doi-asserted-by":"publisher","first-page":"4747","DOI":"10.1016\/j.tcs.2011.05.004","volume":"412","author":"R-W Hung","year":"2011","unstructured":"Hung R-W (2011) Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes. Theor Comput Sci 412:4747\u20134753. https:\/\/doi.org\/10.1016\/j.tcs.2011.05.004","journal-title":"Theor Comput Sci"},{"key":"652_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft JE, Karp RM (1973) An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J Comp 2:225\u2013231. https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J Comp"},{"key":"652_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 CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671\u2013680. https:\/\/doi.org\/10.1126\/science.220.4598.671","journal-title":"Science"},{"key":"652_CR22","doi-asserted-by":"publisher","unstructured":"Kozlova A, Nikolaev A (2019) Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope. In: Khachay M, Kochetov Y, Pardalos P (eds) Mathematical optimization theory and operations research. MOTOR 2019. LNCS, vol 11548, pp 374\u2013389. https:\/\/doi.org\/10.1007\/978-3-030-22629-9_26","DOI":"10.1007\/978-3-030-22629-9_26"},{"key":"652_CR23","doi-asserted-by":"publisher","unstructured":"Krarup J (1995) The peripatetic salesman and some related unsolved problems. In: Roy B (ed) Combinatorial programming: methods and applications. NATO Advanced study institutes series (Series C-Mathematical and physical sciences), vol 19, pp 173\u2013178. https:\/\/doi.org\/10.1007\/978-94-011-7557-9_8","DOI":"10.1007\/978-94-011-7557-9_8"},{"key":"652_CR24","doi-asserted-by":"publisher","first-page":"359","DOI":"10.2298\/YJOR180515016L","volume":"29","author":"NI Lawrance Amaldass","year":"2019","unstructured":"Lawrance Amaldass NI, Lucas C, Mladenovic N (2019) Variable neighbourhood search for financial derivative problem. Yugosl J Oper Res 29:359\u2013373. https:\/\/doi.org\/10.2298\/YJOR180515016L","journal-title":"Yugosl J Oper Res"},{"key":"652_CR25","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF02295996","volume":"12","author":"Q McNemar","year":"1947","unstructured":"McNemar Q (1947) Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika 12:153\u2013157. https:\/\/doi.org\/10.1007\/BF02295996","journal-title":"Psychometrika"},{"key":"652_CR26","doi-asserted-by":"publisher","unstructured":"Micali S, Vazirani VV (1980) An $$O({\\sqrt{|V|}}\\cdot |E|)$$ algorithm for finding maximum matching in general graphs. In: Proceedings 21st IEEE symposium foundations of computer science, pp 17\u201327. https:\/\/doi.org\/10.1109\/SFCS.1980.12","DOI":"10.1109\/SFCS.1980.12"},{"key":"652_CR27","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s10732-017-9364-7","volume":"26","author":"M Mladenovi\u0107","year":"2020","unstructured":"Mladenovi\u0107 M, Delot T, Laporte G, Wilbaut C (2020) The parking allocation problem for connected vehicles. J Heuristics 26:377\u2013399. https:\/\/doi.org\/10.1007\/s10732-017-9364-7","journal-title":"J Heuristics"},{"key":"652_CR28","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107 N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097\u20131100. https:\/\/doi.org\/10.1016\/S0305-0548(97)00031-2","journal-title":"Comput Oper Res"},{"key":"652_CR29","doi-asserted-by":"publisher","unstructured":"Nikolaev A (2019) On vertex adjacencies in the polytope of pyramidal tours with step-backs. In: Khachay M, Kochetov Y, Pardalos P (eds) Mathematical optimization theory and operations research. MOTOR 2019. LNCS, vol 11548, pp 247\u2013263. https:\/\/doi.org\/10.1007\/978-3-030-22629-9_18","DOI":"10.1007\/978-3-030-22629-9_18"},{"key":"652_CR30","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF01585502","volume":"7","author":"MW Padberg","year":"1974","unstructured":"Padberg MW, Rao MR (1974) The travelling salesman problem and a class of polyhedra of diameter two. Math Program 7:32\u201345. https:\/\/doi.org\/10.1007\/BF01585502","journal-title":"Math Program"},{"key":"652_CR31","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01588973","volume":"14","author":"CH Papadimitriou","year":"1978","unstructured":"Papadimitriou CH (1978) The adjacency relation on the traveling salesman polytope is NP-Complete. Math Program 14:312\u2013324. https:\/\/doi.org\/10.1007\/BF01588973","journal-title":"Math Program"},{"key":"652_CR32","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0166-218X(84)90101-X","volume":"8","author":"B P\u00e9roche","year":"1984","unstructured":"P\u00e9roche B (1984) NP-completeness of some problems of partitioning and covering in graphs. Discrete Appl Math 8:195\u2013208. https:\/\/doi.org\/10.1016\/0166-218X(84)90101-X","journal-title":"Discrete Appl Math"},{"key":"652_CR33","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0130021","volume":"30","author":"MR Rao","year":"1976","unstructured":"Rao MR (1976) Adjacency of the traveling salesman tours and 0\u20131 vertices. SIAM J Appl Math 30:191\u2013198. https:\/\/doi.org\/10.1137\/0130021","journal-title":"SIAM J Appl Math"},{"key":"652_CR34","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0895480196312462","volume":"11","author":"FJ Rispoli","year":"1998","unstructured":"Rispoli FJ, Cosares S (1998) A bound of $$4$$ for the diameter of the symmetric traveling salesman polytope. SIAM J Discrete Math 11:373\u2013380. https:\/\/doi.org\/10.1137\/S0895480196312462","journal-title":"SIAM J Discrete Math"},{"key":"652_CR35","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 (1993) The skeleton of the symmetric traveling salesman polytope. Discrete Appl Math 43:63\u201374. https:\/\/doi.org\/10.1016\/0166-218X(93)90169-O","journal-title":"Discrete Appl Math"},{"key":"652_CR36","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","volume":"3","author":"AG Thomason","year":"1978","unstructured":"Thomason AG (1978) Hamiltonian cycles and uniquely edge colourable graphs. Ann Discrete Math 3:259\u2013268. https:\/\/doi.org\/10.1016\/S0167-5060(08)70511-9","journal-title":"Ann Discrete Math"},{"key":"652_CR37","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte WT (1954) A short proof of the factor theorem for finite graphs. Can J Math 6:347\u2013352. https:\/\/doi.org\/10.4153\/CJM-1954-033-3","journal-title":"Can J Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00652-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00652-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00652-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T02:08:22Z","timestamp":1632967702000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00652-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["652"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00652-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"18 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}