{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:09:47Z","timestamp":1773655787923,"version":"3.50.1"},"reference-count":14,"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\/s0146411622070173","type":"journal-article","created":{"date-parts":[[2023,2,19]],"date-time":"2023-02-19T09:03:26Z","timestamp":1676797406000},"page":"788-799","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["NP-Completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k \u2265 3"],"prefix":"10.3103","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0980-2507","authenticated-orcid":false,"given":"A. V.","family":"Smirnov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1627","published-online":{"date-parts":[[2023,2,19]]},"reference":[{"key":"7532_CR1","doi-asserted-by":"publisher","first-page":"625","DOI":"10.3103\/S0146411618070234","volume":"52","author":"A.V. Smirnov","year":"2018","unstructured":"Smirnov, A.V., The shortest path problem for a multiple graph, Autom. Control Comput. Sci., 2018, vol. 52, no.\u00a07, pp. 625\u2013633. https:\/\/doi.org\/10.3103\/S0146411618070234","journal-title":"Autom. Control Comput. Sci."},{"key":"7532_CR2","doi-asserted-by":"publisher","first-page":"871","DOI":"10.3103\/S0146411618070325","volume":"52","author":"A.V. Smirnov","year":"2018","unstructured":"Smirnov, A.V., The spanning tree of a divisible multiple graph, Autom. Control Comput. Sci., 2018, vol. 52, no.\u00a07, pp. 871\u2013879. https:\/\/doi.org\/10.3103\/S0146411618070325","journal-title":"Autom. Control Comput. Sci."},{"key":"7532_CR3","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 1956, vol. 7, no. 1, pp. 48\u201350. https:\/\/doi.org\/10.1090\/S0002-9939-1956-0078686-7","journal-title":"Proc. Am. Math. Soc."},{"key":"7532_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C., Introduction to Algorithms, The\u00a0MIT Press, 2009, 3rd ed."},{"key":"7532_CR5","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge C., Graphs and Hypergraphs, North-Holland, 1973."},{"key":"7532_CR6","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-9236(99)00006-8","volume":"25","author":"A. Basu","year":"1999","unstructured":"Basu, A. and Blanning, R.W., Metagraphs in workflow support systems, Decis. Support Syst., 1999, vol. 25, no.\u00a03, pp. 199\u2013208. https:\/\/doi.org\/10.1016\/S0167-9236(99)00006-8","journal-title":"Decis. Support Syst."},{"key":"7532_CR7","doi-asserted-by":"publisher","unstructured":"Basu, A. and Blanning, R.W., Metagraphs and Their Applications, Integrated Series in Information Systems, vol.\u00a015, New York: Springer, 2007. \u00a0https:\/\/doi.org\/10.1007\/978-0-387-37234-1","DOI":"10.1007\/978-0-387-37234-1"},{"key":"7532_CR8","first-page":"60","volume":"3","author":"V.S. Rublev","year":"2011","unstructured":"Rublev, V.S. and Smirnov, A.V., Flows in multiple networks, Yaroslavsky Pedagog. Vestn., 2011, vol. 3, no. 2, pp.\u00a060\u201368.","journal-title":"Yaroslavsky Pedagog. Vestn."},{"key":"7532_CR9","doi-asserted-by":"publisher","first-page":"527","DOI":"10.3103\/S0146411616070191","volume":"50","author":"A.V. Smirnov","year":"2016","unstructured":"Smirnov, A.V., The problem of finding the maximum multiple flow in the divisible network and its special cases, Autom. Control Comput. Sci., 2016, vol. 50, no. 7, pp. 527\u2013535. https:\/\/doi.org\/10.3103\/S0146411616070191","journal-title":"Autom. Control Comput. Sci."},{"key":"7532_CR10","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R. and Fulkerson, D.R., Flows in Networks, Princeton Univ. Press, 1962."},{"key":"7532_CR11","first-page":"72","volume":"17","author":"V.S. Roublev","year":"2010","unstructured":"Roublev, V.S. and Smirnov, A.V., The problem of integer-valued balancing of a three-dimensional matrix and algorithms of its solution, Model. Anal. Inf. Sist., 2010, vol. 17, no. 2, pp. 72\u201398.","journal-title":"Model. Anal. Inf. Sist."},{"key":"7532_CR12","doi-asserted-by":"publisher","first-page":"558","DOI":"10.3103\/S0146411617070185","volume":"51","author":"A.V. Smirnov","year":"2017","unstructured":"Smirnov, A.V., Network model for the problem of integer balancing of a four-dimensional matrix, Autom. Control Comput. Sci., vol. 51, no. 7, pp. 558\u2013566, 2017. \u00a0https:\/\/doi.org\/10.3103\/S0146411617070185","journal-title":"Autom. Control Comput. Sci."},{"key":"7532_CR13","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, W.\u00a0H. Freeman and Company, 1979."},{"key":"7532_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems, Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R., Reducibility among combinatorial problems, Complexity of Computer Computations, Miller, R.E. and Thatcher, J.W., Eds., Plenum, 1972, pp. 85\u2013103. \u00a0https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411622070173.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411622070173","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411622070173.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:05:38Z","timestamp":1773612338000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411622070173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":14,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["7532"],"URL":"https:\/\/doi.org\/10.3103\/s0146411622070173","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":"1 March 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 author declares that he has no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}