{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T23:01:53Z","timestamp":1773615713449,"version":"3.50.1"},"reference-count":29,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.3103\/s0146411622070082","type":"journal-article","created":{"date-parts":[[2023,2,19]],"date-time":"2023-02-19T09:03:26Z","timestamp":1676797406000},"page":"688-700","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-Regular Multigraph"],"prefix":"10.3103","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1881-0207","authenticated-orcid":false,"given":"A. V.","family":"Korostil","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4705-2409","authenticated-orcid":false,"given":"A. V.","family":"Nikolaev","sequence":"additional","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2023,2,19]]},"reference":[{"key":"7524_CR1","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.dam.2016.10.024","volume":"218","author":"N.E. Aguilera","year":"2017","unstructured":"Aguilera, N.E., Katz, R.D., and Tolomei, P.B., Vertex adjacencies in the set covering polyhedron, Discrete Appl. Math., 2017, vol. 218, pp. 40\u201356. https:\/\/doi.org\/10.1016\/j.dam.2016.10.024","journal-title":"Discrete Appl. Math."},{"key":"7524_CR2","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"D.L. Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., and Cook, W.J., The Traveling Salesman Problem: A Computational Study, Princeton Univ. Press, 2006."},{"key":"7524_CR3","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1016\/j.disc.2005.11.030","volume":"306","author":"T.S. Arthanari","year":"2006","unstructured":"Arthanari, T.S., On pedigree polytopes and Hamiltonian cycles, Discrete Math., 2006, vol.\u00a0306, no. 14, pp.\u00a01474\u20131492. https:\/\/doi.org\/10.1016\/j.disc.2005.11.030","journal-title":"Discrete Math."},{"key":"7524_CR4","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.disopt.2013.07.001","volume":"10","author":"T.S. Arthanari","year":"2013","unstructured":"Arthanari, T.S., Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, Discrete Optim., 2013, vol. 10, no. 3, pp. 224\u2013232. \u00a0https:\/\/doi.org\/10.1016\/j.disopt.2013.07.001","journal-title":"Discrete Optim."},{"key":"7524_CR5","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.1109\/TC.2003.1234525","volume":"52","author":"M.M. Bae","year":"2003","unstructured":"Bae, M.M. and Bose, M., Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes, IEEE Trans. Comput., 2003, vol. 52, no. 10, pp. 1271\u20131284. \u00a0https:\/\/doi.org\/10.1109\/TC.2003.1234525","journal-title":"IEEE Trans. Comput."},{"key":"7524_CR6","doi-asserted-by":"publisher","first-page":"4253","DOI":"10.1016\/j.disc.2008.12.027","volume":"309","author":"R.F. Bailey","year":"2009","unstructured":"Bailey, R.F., Error-correcting codes from permutation groups, Discrete Math., 2009, vol.\u00a0309, no. 13, pp. 4253\u20134265. https:\/\/doi.org\/10.1016\/j.disc.2008.12.027","journal-title":"Discrete Math."},{"key":"7524_CR7","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/opre.33.3.527","volume":"33","author":"M.L. Balinski","year":"1985","unstructured":"Balinski, M.L., Signature methods for the assignment problem, Oper. Res., 1985, vol. 33, no. 3, pp. 527\u2013536. https:\/\/doi.org\/10.1287\/opre.33.3.527","journal-title":"Oper. Res."},{"key":"7524_CR8","doi-asserted-by":"publisher","first-page":"7863650","DOI":"10.1155\/2016\/7863650","volume":"2016","author":"V. Bondarenko","year":"2016","unstructured":"Bondarenko, V. and Nikolaev, A., On graphs of the cone decompositions for the min-cut and max-cut problems, Int. J. Math. Math. Sci., 2016, vol. 2016, p. 7863650. \u00a0https:\/\/doi.org\/10.1155\/2016\/7863650","journal-title":"Int. J. Math. Math. Sci."},{"key":"7524_CR9","first-page":"1137","volume":"44","author":"V.A. Bondarenko","year":"1983","unstructured":"Bondarenko, V.A., Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms, Autom. Remote Control, 1983, vol. 44, no. 9, pp.\u00a01137\u20131142.","journal-title":"Autom. Remote Control"},{"key":"7524_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1134\/S1990478918010027","volume":"12","author":"V.A. Bondarenko","year":"2018","unstructured":"Bondarenko, V.A. and Nikolaev, A.V., On the skeleton of the polytope of pyramidal tours, J. Appl. Ind. Math., 2018, vol. 12, no. 1, pp. 9\u201318. https:\/\/doi.org\/10.1134\/S1990478918010027","journal-title":"J. Appl. Ind. Math."},{"key":"7524_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(87)90017-5","volume":"18","author":"C.R. Chegireddy","year":"1987","unstructured":"Chegireddy, C.R. and Hamacher, H.W., Algorithms for finding K-best perfect matchings, Discrete Appl. Math., 1987, vol. 18, no. 2, pp. 155\u2013165. https:\/\/doi.org\/10.1016\/0166-218X(87)90017-5","journal-title":"Discrete Appl. Math."},{"key":"7524_CR12","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., and Zhu, M.Y., Tools for privacy preserving distributed data mining, ACM SIGKDD Explor. Newsl., 2002, vol. 4, no. 2, pp. 28\u201334. https:\/\/doi.org\/10.1145\/772862.772867","journal-title":"ACM SIGKDD Explor. Newsl."},{"key":"7524_CR13","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.fss.2009.05.004","volume":"161","author":"E.F. Combarro","year":"2010","unstructured":"Combarro, E.F. and Miranda, P., Adjacency on the order polytope with applications to the theory of fuzzy measures, Fuzzy Sets Syst., 2010, vol. 161, no. 5, pp. 619\u2013641. https:\/\/doi.org\/10.1016\/j.fss.2009.05.004","journal-title":"Fuzzy Sets Syst."},{"key":"7524_CR14","doi-asserted-by":"publisher","first-page":"393","DOI":"10.2307\/166695","volume":"2","author":"G. Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., and Johnson, S., Solution of a large-scale traveling-salesman problem, J. Oper. Res. Soc. Am., 1954, vol. 2, no. 4, pp. 393\u2013410. https:\/\/doi.org\/10.2307\/166695","journal-title":"J. Oper. Res. Soc. Am."},{"key":"7524_CR15","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1137\/0206011","volume":"6","author":"H.N. Gabow","year":"1977","unstructured":"Gabow, H.N., Two algorithms for generating weighted spanning trees in order, SIAM J. Comput., 1977, vol. 6, no. 1, pp. 139\u2013150. https:\/\/doi.org\/10.1137\/0206011","journal-title":"SIAM J. Comput."},{"key":"7524_CR16","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., and Sudakov, B., The number of Hamiltonian decompositions of regular graphs, Israel J. Math., 2017, vol. 222, no. 1, pp. 91\u2013108. https:\/\/doi.org\/10.1007\/s11856-017-1583-y","journal-title":"Israel J. Math."},{"key":"7524_CR17","unstructured":"Gr\u00f6tschel, M. and Padberg, M., Polyhedral theory, The Traveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization, Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., Eds., Chichester: John Wiley, 1985, pp. 251\u2013305."},{"key":"7524_CR18","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., Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes, Theor. Comput. Sci., 2011, vol. 412, no. 35, pp. 4747\u20134753. https:\/\/doi.org\/10.1016\/j.tcs.2011.05.004","journal-title":"Theor. Comput. Sci."},{"key":"7524_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jctb.2000.1991","volume":"81","author":"J.H. Kim","year":"2001","unstructured":"Kim, J.H. and Wormald, N.C., Random matchings which induce Hamilton cycles and hamiltonian decompositions of random regular graphs, J. Combinatorial Theory, Ser. B, 2001, vol. 81, no. 1, pp. 20\u201344. https:\/\/doi.org\/10.1006\/jctb.2000.1991","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"7524_CR20","doi-asserted-by":"publisher","unstructured":"Knuth, D.E., The Art of Computer Programming, vol. 2: Seminumerical Algorithms, Addison-Wesley, 1997, 3rd ed. https:\/\/doi.org\/10.5555\/270146","DOI":"10.5555\/270146"},{"key":"7524_CR21","first-page":"91","volume":"12","author":"A.V. Korostil","year":"2020","unstructured":"Korostil, A.V. and Nikolaev, A.V., Backtracking algorithm to construct the Hamiltonian decomposition of a 4-regular multigraph, Zam. Inf. Mat., 2020, vol. 12, pp. 91\u201397.","journal-title":"Zam. Inf. Mat."},{"key":"7524_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-22629-9_26","volume-title":"Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope, Mathematical Optimization Theory and Operations Research. MOTOR 2019, Khachay, M., Kochetov, Y., and Pardalos, P.","author":"A. Kozlova","year":"2019","unstructured":"Kozlova, A. and Nikolaev, A., Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope, Mathematical Optimization Theory and Operations Research. MOTOR 2019, Khachay, M., Kochetov, Y., and Pardalos, P., Lecture Notes in Computer Science, vol. 11548, Cham: Springer, 2019, pp.\u00a0374\u2013389. https:\/\/doi.org\/10.1007\/978-3-030-22629-9_26"},{"key":"7524_CR23","series-title":"NATO Advanced Study Institutes Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-7557-9_8","volume-title":"The peripatetic salesman and some related unsolved problems, Combinatorial Programming: Methods and Applications","author":"J. Krarup","year":"1995","unstructured":"Krarup, J., The peripatetic salesman and some related unsolved problems, Combinatorial Programming: Methods and Applications, Roy, B., Eds., NATO Advanced Study Institutes Series, vol. 19, Dordrecht: Springer, 1995, pp.\u00a0173\u2013178. https:\/\/doi.org\/10.1007\/978-94-011-7557-9_8"},{"key":"7524_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-22629-9_18","volume-title":"On vertex adjacencies in the polytope of pyramidal tours with step-backs, Mathematical Optimization Theory and Operations Research. MOTOR 2019, Khachay, M., Kochetov, Y., and Pardalos, P.","author":"A. Nikolaev","year":"2019","unstructured":"Nikolaev, A., On vertex adjacencies in the polytope of pyramidal tours with step-backs, Mathematical Optimization Theory and Operations Research. MOTOR 2019, Khachay, M., Kochetov, Y., and Pardalos, P., Lecture Notes in Computer Science, vol. 11548, Cham: Springer, 2019, pp. 247\u2013263. https:\/\/doi.org\/10.1007\/978-3-030-22629-9_18"},{"key":"7524_CR25","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s10878-020-00652-7","volume":"42","author":"A. Nikolaev","year":"2021","unstructured":"Nikolaev, A. and Kozlova, A., Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search, J.\u00a0Combinatorial Optim., 2021, vol. 42, no. 2, pp. 212\u2013230. https:\/\/doi.org\/10.1007\/s10878-020-00652-7","journal-title":"J.\u00a0Combinatorial Optim."},{"key":"7524_CR26","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01588973","volume":"14","author":"C.H. Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H., The adjacency relation on the traveling salesman polytope is NP-complete, Math. Program., 1978, vol. 14, no. 1, pp. 312\u2013324. https:\/\/doi.org\/10.1007\/BF01588973","journal-title":"Math. Program."},{"key":"7524_CR27","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., NP-completeness of some problems of partitioning and covering in graphs, Discrete Appl. Math., 1984, vol. 8, no. 2, pp. 195\u2013208. https:\/\/doi.org\/10.1016\/0166-218X(84)90101-X","journal-title":"Discrete Appl. Math."},{"key":"7524_CR28","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0130021","volume":"30","author":"M.R. Rao","year":"1976","unstructured":"Rao, M.R., Adjacency of the traveling salesman tours and $0 - 1$ vertices, SIAM J. Appl. Math., 1976, vol. 30, no. 2, pp. 191\u2013198. https:\/\/doi.org\/10.1137\/0130021","journal-title":"SIAM J. Appl. Math."},{"key":"7524_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The Algorithm Design Manual","author":"S.S. Skiena","year":"2008","unstructured":"Skiena, S.S., The Algorithm Design Manual, London: Springer, 2008, 2nd ed. https:\/\/doi.org\/10.1007\/978-1-84800-070-4"}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411622070082.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411622070082","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411622070082.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:03:37Z","timestamp":1773612217000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411622070082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":29,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["7524"],"URL":"https:\/\/doi.org\/10.3103\/s0146411622070082","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"15 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}