{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:50Z","timestamp":1740145190074,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100007675","name":"Laboratory of Algorithms and Technologies for Networks Analysis","doi-asserted-by":"publisher","award":["-"],"award-info":[{"award-number":["-"]}],"id":[{"id":"10.13039\/501100007675","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002261","name":"\u0420\u043e\u0441\u0441\u0438\u0439\u0441\u043a\u0438\u0439 \u0424\u043e\u043d\u0434 \u0424\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439","doi-asserted-by":"publisher","award":["20-51-04001"],"award-info":[{"award-number":["20-51-04001"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s11590-021-01771-8","type":"journal-article","created":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T15:02:28Z","timestamp":1624201348000},"page":"481-496","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On partial descriptions of K\u00f6nig graphs for odd paths and all their spanning supergraphs"],"prefix":"10.1007","volume":"16","author":[{"given":"Dmitry B.","family":"Mokeev","sequence":"first","affiliation":[]},{"given":"Dmitry S.","family":"Malyshev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"issue":"4","key":"1771_CR1","first-page":"3","volume":"19","author":"VE Alekseev","year":"2012","unstructured":"Alekseev, V.E., Mokeev, D.B.: K\u00f6nig graphs with respect to the 3-path. Diskretnyi Analiz i Issledovanie Operatsii. 19(4), 3\u201314 (2012). (in Russian)","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii."},{"key":"1771_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2015.10.002","volume":"204","author":"VE Alekseev","year":"2016","unstructured":"Alekseev, V.E., Mokeev, D.B.: K\u00f6nig graphs for 3-paths and 3-cycles. Discrete Appl. Math. 204, 1\u20135 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"12","key":"1771_CR3","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum $$k$$-path vertex cover. Discrete Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discrete Appl. Math."},{"key":"1771_CR4","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/1.9780898717105","volume-title":"Combinatorial Optimization: Packing and Covering","author":"G Cornu\u00e9jols","year":"2001","unstructured":"Cornu\u00e9jols, G.: Combinatorial Optimization: Packing and Covering, p. 132. SIAM, New York (2001)"},{"key":"1771_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0012-365X(79)90066-9","volume":"27","author":"RW Deming","year":"1979","unstructured":"Deming, R.W.: Independence numbers of graphs \u2013 an extension of the K\u00f6nig-Egervary theorem. Discrete Math. 27, 23\u201333 (1979)","journal-title":"Discrete Math."},{"key":"1771_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.dam.2014.10.033","volume":"184","author":"NS Devi","year":"2015","unstructured":"Devi, N.S., Mane, A.C., Mishra, S.: Computational complexity of minimum $$P_k$$ vertex cover problem for regular and $$K_{1,4}$$-free graphs. Discrete Appl. Math. 184, 114\u2013121 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1771_CR7","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"1771_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"key":"1771_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/S1571-0653(05)80154-4","volume":"5","author":"P Hell","year":"2000","unstructured":"Hell, P.: Graph packing. Electron. Notes Discrete Math. 5, 170\u2013173 (2000)","journal-title":"Electron. Notes Discrete Math."},{"issue":"50","key":"1771_CR10","doi-asserted-by":"publisher","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"F Kardo\u0161","year":"2011","unstructured":"Kardo\u0161, F., Katreni\u010d, J., Schiermeyer, I.: On computing the minimum 3-path vertex cover and dissociation number of graphs. Theor. Comput. Sci. 412(50), 7009\u20137017 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1771_CR11","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Hell, P.(1978): On the completeness of a generalized matching problem. In: Lipton R. et al (eds.). Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, New York pp. 240\u2013245","DOI":"10.1145\/800133.804353"},{"issue":"5","key":"1771_CR12","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00373-008-0807-7","volume":"24","author":"A Kosowski","year":"2008","unstructured":"Kosowski, A., Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Combinatorial and computational aspects of graph packing and graph decomposition. Gr. Comb. 24(5), 461\u2013468 (2008)","journal-title":"Gr. Comb."},{"issue":"10","key":"1771_CR13","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1080\/00207160.2014.881476","volume":"91","author":"Y Li","year":"2014","unstructured":"Li, Y., Tu, J.: A 2-approximation algorithm for the vertex cover $$P_k$$ problem in cubic graphs. Int. J. Comput. Math. 91(10), 2103\u20132108 (2014)","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"1771_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1134\/S1990478919010101","volume":"13","author":"DS Malyshev","year":"2019","unstructured":"Malyshev, D.S., Mokeev, D.B.: K\u00f6nig graphs with respect to the 4-path and its spanning supergraphs. J. Appl. Ind. Math. 13(1), 85\u201392 (2019)","journal-title":"J. Appl. Ind. Math."},{"issue":"1","key":"1771_CR15","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1007\/BF01759074","volume":"6","author":"S Masuyama","year":"1991","unstructured":"Masuyama, S., Ibaraki, T.: Chain packing in graphs. Algorithmica 6(1), 826\u2013839 (1991)","journal-title":"Algorithmica"},{"key":"1771_CR16","unstructured":"Mokeev, D.B.: $$P_q$$-K\u00f6nig extended forests and cycles. In: Kononov, A et al. (eds.) Proceedings of the 9th International Conference on Discrete Optimization and Operations Research (Vladivostok, September 19\u201323, 2016), pp. 86\u201395. Springer (2016)"},{"issue":"3","key":"1771_CR17","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1134\/S1990478917030139","volume":"11","author":"DB Mokeev","year":"2017","unstructured":"Mokeev, D.B.: On K\u00f6nig graphs with respect to $$P_4$$. J. Appl. Ind. Math. 11(3), 421\u2013430 (2017)","journal-title":"J. Appl. Ind. Math."},{"issue":"2","key":"1771_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1134\/S1990478920020143","volume":"14","author":"DB Mokeev","year":"2020","unstructured":"Mokeev, D.B., Malyshev, D.S.: On the K\u00f6nig graphs for the 5-path and its spanning supergraphs. J. Appl. Ind. Math. 14(2), 369\u2013384 (2020)","journal-title":"J. Appl. Ind. Math."},{"issue":"6","key":"1771_CR19","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1007\/s11590-019-01475-0","volume":"14","author":"DB Mokeev","year":"2020","unstructured":"Mokeev, D.B., Malyshev, D.S.: A polynomial-time algorithm of finding a minimum $$k$$-path vertex cover and a maximum $$k$$-path packing in some graphs. Optim. Lett. 14(6), 1317\u20131322 (2020)","journal-title":"Optim. Lett."},{"key":"1771_CR20","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/0095-8956(79)90085-6","volume":"27","author":"F Sterboul","year":"1979","unstructured":"Sterboul, F.: A characterization of graphs in which the transversal number equals the matching number. J. Comb. Theory, Ser. B 27, 228\u2013229 (1979)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"50","key":"1771_CR21","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"J Tu","year":"2011","unstructured":"Tu, J., Zhou, W.: A primal-dual approximation algorithm for the vertex cover $$P_3$$ problem. Theor. Comput. Sci. 412(50), 7044\u20137048 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1771_CR22","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cosrev.2007.07.002","volume":"1","author":"R Yuster","year":"2007","unstructured":"Yuster, R.: Combinatorial and computational aspects of graph packing and graph decomposition. Comput. Sci. Rev. 1, 12\u201326 (2007)","journal-title":"Comput. Sci. Rev."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01771-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01771-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01771-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T13:29:13Z","timestamp":1645018153000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01771-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,20]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1771"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01771-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,6,20]]},"assertion":[{"value":"4 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}