{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:05:24Z","timestamp":1773655524800,"version":"3.50.1"},"reference-count":15,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"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":[[2017,12]]},"DOI":"10.3103\/s0146411617070033","type":"journal-article","created":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T03:40:46Z","timestamp":1518666046000},"page":"682-688","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["1-Skeletons of the Spanning Tree Problems with Additional Constraints"],"prefix":"10.3103","volume":"51","author":[{"given":"V. A.","family":"Bondarenko","sequence":"first","affiliation":[]},{"given":"A. V.","family":"Nikolaev","sequence":"additional","affiliation":[]},{"given":"D. A.","family":"Shovgenov","sequence":"additional","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2018,2,7]]},"reference":[{"key":"6671_CR1","first-page":"95","volume-title":"Modeli issledovaniya operacii v vychislitel\u2019nykh sistemakh","author":"Y.A. Belov","year":"1985","unstructured":"Belov, Y.A., On clique number of matroid skeleton, in Modeli issledovaniya operacii v vychislitel\u2019nykh sistemakh (Models of Operations Research in Computer Systems), Yaroslavl, 1985, pp. 95\u2013100"},{"issue":"1","key":"6671_CR2","first-page":"22","volume":"328","author":"V.A. Bondarenko","year":"1993","unstructured":"Bondarenko, V.A., Complexity bounds for combinatorial optimization problems in one class of algorithms, Russ. Acad. Sci. Dokl. Math., 1993, vol. 328, no 1, pp. 22\u201324.","journal-title":"Russ. Acad. Sci. Dokl. Math."},{"key":"6671_CR3","volume-title":"Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoi optimizatsii","author":"V.A. Bondarenko","year":"2008","unstructured":"Bondarenko, V.A. and Maksimenko, A.N., Geometricheskie konstruktsii i slozhnost\u2019 v kombinatornoi optimizatsii (Geometric Constructs and Complexity in Combinatorial Optimization), Moscow: LKI, 2008."},{"issue":"2","key":"6671_CR4","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1134\/S1064562413050062","volume":"88","author":"V.A. Bondarenko","year":"2013","unstructured":"Bondarenko, V.A. and Nikolaev, A.V., Combinatorial and geometric properties of the max-cut and min-cut problems, Dokl. Math., 2013, vol. 88, no. 2, pp. 516\u2013517.","journal-title":"Dokl. Math."},{"key":"6671_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1148-8","volume-title":"An Introduction to Convex Polytopes","author":"A. Brondsted","year":"1983","unstructured":"Brondsted, A., An Introduction to Convex Polytopes, Springer-Verlag, 1983."},{"issue":"1","key":"6671_CR6","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/S0377-2217(96)00327-X","volume":"104","author":"L.M. Fernandes","year":"1998","unstructured":"Fernandes, L.M. and Gouveia, L., Minimal spanning trees with a constraint on the number of leaves, Eur. J. Oper. Res., 1998, vol. 104, no. 1, pp. 250\u2013261.","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"6671_CR7","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1002\/net.20001","volume":"43","author":"T. Fujie","year":"2004","unstructured":"Fujie, T., The maximum-leaf spanning tree problem: Formulations and facets, Networks, 2004, vol. 43, no. 4, pp. 212\u2013223.","journal-title":"Networks"},{"key":"6671_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: W. H. Freeman & Co, 1979."},{"key":"6671_CR9","first-page":"273","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"M.X. Goemans","year":"2006","unstructured":"Goemans, M.X., Minimum bounded-degree spanning trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 273\u2013282"},{"issue":"3","key":"6671_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"R.K. Martin","year":"1991","unstructured":"Martin, R.K., Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett., 1991, vol. 10, no. 3, pp. 119\u2013128.","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"6671_CR11","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. Progr., 1978, vol. 14, no. 1, pp. 312\u2013324.","journal-title":"Math. Progr."},{"key":"6671_CR12","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Upper Saddle River, NJ: Prentice-Hall, Inc., 1982."},{"issue":"2","key":"6671_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ipl.2004.12.016","volume":"94","author":"M.S. Rahman","year":"2005","unstructured":"Rahman, M.S. and Kaykobad, M., Complexities of some interesting problems on spanning trees Inf. Process. Lett., 2005, vol. 94, no. 2, pp. 93\u201397.","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"6671_CR14","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G. Salamon","year":"2008","unstructured":"Salamon, G. and Wiener, G., On finding spanning trees with few leaves, Inf. Process. Lett., 2008, vol. 105, no. 5, pp. 164\u2013169.","journal-title":"Inf. Process. Lett."},{"key":"6671_CR15","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/1250790.1250887","volume-title":"Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing","author":"M. Singh","year":"2007","unstructured":"Singh, M. and Lau, L.C., Approximating minimum bounded degree spanning trees to within one of optimal, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 661\u2013670"}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411617070033","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411617070033.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411617070033.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T21:57:53Z","timestamp":1773611873000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411617070033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":15,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["6671"],"URL":"https:\/\/doi.org\/10.3103\/s0146411617070033","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]},"assertion":[{"value":"30 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}