{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:35:15Z","timestamp":1768685715104,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T00:00:00Z","timestamp":1678060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T00:00:00Z","timestamp":1678060800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NSERC Canada"},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP17K00016"],"award-info":[{"award-number":["KAKENHI JP17K00016"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP18H04091"],"award-info":[{"award-number":["KAKENHI JP18H04091"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP18H04091"],"award-info":[{"award-number":["KAKENHI JP18H04091"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP19K12098"],"award-info":[{"award-number":["KAKENHI JP19K12098"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP20H05794"],"award-info":[{"award-number":["KAKENHI JP20H05794"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP20K11666"],"award-info":[{"award-number":["KAKENHI JP20K11666"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP21H05857"],"award-info":[{"award-number":["KAKENHI JP21H05857"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["KAKENHI JP21K11755"],"award-info":[{"award-number":["KAKENHI JP21K11755"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"publisher","award":["CREST JPMJCR1402"],"award-info":[{"award-number":["CREST JPMJCR1402"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"publisher","award":["CREST JPMJCR1402"],"award-info":[{"award-number":["CREST JPMJCR1402"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s00453-023-01106-2","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T09:04:04Z","timestamp":1678093444000},"page":"3348-3375","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Path Cover Problems with Length Cost"],"prefix":"10.1007","volume":"85","author":[{"given":"Kenya","family":"Kobayashi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4260-7818","authenticated-orcid":false,"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4676-5167","authenticated-orcid":false,"given":"Toshiki","family":"Saitoh","sequence":"additional","affiliation":[]},{"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[]},{"given":"Tadatoshi","family":"Utashima","sequence":"additional","affiliation":[]},{"given":"Tsuyoshi","family":"Yagita","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"issue":"2","key":"1106_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebra Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebra Discret. Methods"},{"issue":"3","key":"1106_CR2","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.disopt.2006.05.008","volume":"3","author":"N Betzler","year":"2006","unstructured":"Betzler, N., Niedermeier, R., Uhlmann, J.: Tree decompositions of graphs: saving memory in dynamic programming. Discret. Optim. 3(3), 220\u2013229 (2006)","journal-title":"Discret. Optim."},{"issue":"3","key":"1106_CR3","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s10878-021-00793-3","volume":"43","author":"Y Chen","year":"2022","unstructured":"Chen, Y., Cai, Y., Liu, L., Chen, G., Goebel, R., Lin, G., Su, B., Zhang, A.: Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph. J. Comb. Optim. 43(3), 571\u2013588 (2022)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"1106_CR4","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/s10878-018-00372-z","volume":"38","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Goebel, R., Lin, G., Su, B., Xu, Y., Zhang, A.: An improved approximation algorithm for the minimum 3-path partition problem. J. Comb. Optim. 38(1), 150\u2013164 (2019)","journal-title":"J. Comb. Optim."},{"key":"1106_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Goebel, R., Lin, G., Liu, L., Su, B., Tong, W., Xu, Y., Zhang, A.: A local search 4\/3-approximation algorithm for the minimum 3-path partition problem. In: Proceedings of 13th FAW 2019, LNCS\u00a011458, pp. 14\u201325, (2019)","DOI":"10.1007\/978-3-030-18126-0_2"},{"key":"1106_CR6","unstructured":"Chen, Y., Goebel, R., Su, B., Tong, W., Xu, Y., Zhang, A.: A $$\\frac{21}{16}$$-approximation for the minimum 3-path partition problem. In: Proceedings of 30th ISAAC 2019, LIPIcs\u00a0212, pp. 46:1\u201346:20, (2019)"},{"key":"1106_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, Springer, (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1106_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, NY (1990)"},{"issue":"3","key":"1106_CR9","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/S0304-3975(02)00577-7","volume":"290","author":"S George","year":"2003","unstructured":"George, S.: On the $$k$$-path partition of graphs. Theor. Comput. Sci. 290(3), 2147\u20132155 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"1106_CR10","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10878-019-00488-w","volume":"39","author":"R G\u00f3mez","year":"2020","unstructured":"G\u00f3mez, R., Wakabayashi, Y.: Nontrivial path covers of graphs: existence, minimization and maximization. J. Comb. Optim. 39, 437\u2013456 (2020)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1106_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0095-8956(03)00027-3","volume":"88","author":"A Kaneko","year":"2003","unstructured":"Kaneko, A.: A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Comb. Theor. Ser. B 88(2), 195\u2013218 (2003)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"3","key":"1106_CR12","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12(3), 601\u2013609 (1983)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1106_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1106_CR14","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1142\/S0219720008003308","volume":"6","author":"J Manuch","year":"2008","unstructured":"Manuch, J., Gaur, D.R.: Fitting protein chains to cubic lattice is NP-complete. J. Bioinf. Comput. Biol. 6(1), 93\u2013106 (2008)","journal-title":"J. Bioinf. Comput. Biol."},{"issue":"5","key":"1106_CR15","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2006.12.004","volume":"35","author":"J Monnot","year":"2007","unstructured":"Monnot, J., Toulouse, S.: The path partition problem and related problems in bipartite graphs. Operat. Res. Lett. 35(5), 677\u2013684 (2007)","journal-title":"Operat. Res. Lett."},{"issue":"1","key":"1106_CR16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.2140\/pjm.1975.58.159","volume":"58","author":"S Noorvash","year":"1975","unstructured":"Noorvash, S.: Covering the vertices of a graph by vertex-disjoint paths. Pac. J. Math. 58(1), 159\u2013168 (1975)","journal-title":"Pac. J. Math."},{"issue":"4","key":"1106_CR17","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.7151\/dmgt.1974","volume":"37","author":"S Zhou","year":"2017","unstructured":"Zhou, S., Wu, J., Zhang, T.: The existence of $$P_{\\ge 3}$$-factor covered graphs. Discuss. Math. Graph Theor. 37(4), 1055\u20131065 (2017)","journal-title":"Discuss. Math. Graph Theor."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01106-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01106-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01106-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T19:02:49Z","timestamp":1698778969000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01106-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,6]]},"references-count":17,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1106"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01106-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,6]]},"assertion":[{"value":"19 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}