{"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":1773655643975,"version":"3.50.1"},"publisher-location":"Cham","reference-count":22,"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_18","type":"book-chapter","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:02:42Z","timestamp":1560283362000},"page":"247-263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Vertex Adjacencies in the Polytope of Pyramidal Tours with Step-Backs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4705-2409","authenticated-orcid":false,"given":"Andrei","family":"Nikolaev","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"18_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, 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":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.disopt.2013.07.001","volume":"10","author":"TS Arthanari","year":"2013","unstructured":"Arthanari, T.S.: Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope. Discrete Optim. 10(3), 224\u2013232 (2013). \n                      https:\/\/doi.org\/10.1016\/j.disopt.2013.07.001","journal-title":"Discrete Optim."},{"issue":"3","key":"18_CR3","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."},{"key":"18_CR4","volume-title":"Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoy optimizatsii (Geometric constructions and complexity in combinatorial optimization)","author":"VA Bondarenko","year":"2008","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":"18_CR5","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":"18_CR6","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":"18_CR7","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."},{"issue":"7","key":"18_CR8","doi-asserted-by":"publisher","first-page":"682","DOI":"10.3103\/s0146411617070033","volume":"51","author":"VA Bondarenko","year":"2017","unstructured":"Bondarenko, V.A., Nikolaev, A.V., Shovgenov, D.A.: 1-skeletons of the spanning tree problems with additional constraints. Autom. Control Comput. Sci. 51(7), 682\u2013688 (2017). \n                      https:\/\/doi.org\/10.3103\/s0146411617070033","journal-title":"Autom. Control Comput. Sci."},{"issue":"7","key":"18_CR9","doi-asserted-by":"publisher","first-page":"576","DOI":"10.3103\/s0146411617070276","volume":"51","author":"VA Bondarenko","year":"2017","unstructured":"Bondarenko, V.A., Nikolaev, A.V., Shovgenov, D.A.: Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems. Autom. Control Comput. Sci. 51(7), 576\u2013585 (2017). \n                      https:\/\/doi.org\/10.3103\/s0146411617070276","journal-title":"Autom. Control Comput. Sci."},{"key":"18_CR10","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":"18_CR11","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 Sets Syst. 161, 619\u2013641 (2010). \n                      https:\/\/doi.org\/10.1016\/j.fss.2009.05.004","journal-title":"Fuzzy Sets Syst."},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0166-218X(98)00048-1","volume":"87","author":"H Enomoto","year":"1998","unstructured":"Enomoto, H., Oda, Y., Ota, K.: Pyramidal tours with step-backs and the asymmetric traveling salesman problem. Discrete Appl. Math. 87, 57\u201365 (1998). \n                      https:\/\/doi.org\/10.1016\/S0166-218X(98)00048-1","journal-title":"Discrete Appl. Math."},{"key":"18_CR13","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":"18_CR14","first-page":"87","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"PC Gilmore","year":"1985","unstructured":"Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. In: Lawler, E., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 87\u2013143. Wiley, Chichester (1985)"},{"key":"18_CR15","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)"},{"key":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-319-71150-8_23","volume-title":"Combinatorial Optimization and Applications","author":"M Khachay","year":"2017","unstructured":"Khachay, M., Neznakhina, K.: Generalized pyramidal tours for the generalized traveling salesman problem. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10627, pp. 265\u2013277. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-71150-8_23"},{"key":"18_CR17","unstructured":"Matsui, T.: NP-completeness of non-adjacency relations on some 0\u20131 polytopes. In: Proceedings of ISORA 1995. Lecture Notes in Operations Research, vol. 1, pp. 249\u2013258 (1995)"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(00)00273-0","volume":"109","author":"Y Oda","year":"2001","unstructured":"Oda, Y.: An asymmetric analogue of van der Veen conditions and the traveling salesman problem. Discrete Appl. Math. 109, 279\u2013292 (2001). \n                      https:\/\/doi.org\/10.1016\/S0166-218X(00)00273-0","journal-title":"Discrete Appl. Math."},{"key":"18_CR19","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":"18_CR20","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."},{"issue":"2","key":"18_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0167-6377(95)00035-6","volume":"18","author":"G Sierksma","year":"1995","unstructured":"Sierksma, G., Teunter, R.H., Tijssen, G.A.: Faces of diameter two on the Hamiltonian cycle polytype. Oper. Res. Lett. 18(2), 59\u201364 (1995). \n                      https:\/\/doi.org\/10.1016\/0167-6377(95)00035-6","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"18_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.21538\/0134-4889-2018-24-2-235-242","volume":"24","author":"\u0420. \u042e. \u0421\u0438\u043c\u0430\u043d\u0447\u0435\u0432","year":"2018","unstructured":"Simanchev, R.Yu.: On the vertex adjacency in a polytope of connected k-factors. Trudy Inst. Mat. i Mekh. UrO RAN 24(2), 235\u2013242 (2018). \n                      https:\/\/doi.org\/10.21538\/0134-4889-2018-24-2-235-242","journal-title":"Trudy Instituta Matematiki i Mekhaniki UrO RAN"}],"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_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:04:18Z","timestamp":1560283458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-22629-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030226282","9783030226299"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22629-9_18","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"}}]}}