{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T12:15:04Z","timestamp":1782562504572,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T00:00:00Z","timestamp":1716854400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T00:00:00Z","timestamp":1716854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["G2022040004L, G2023016016L"],"award-info":[{"award-number":["G2022040004L, G2023016016L"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["G2022040004L, G2023016016L"],"award-info":[{"award-number":["G2022040004L, G2023016016L"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP21K11755, JP17K00016"],"award-info":[{"award-number":["JP21K11755, JP17K00016"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s00453-024-01242-3","type":"journal-article","created":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T13:38:51Z","timestamp":1716903531000},"page":"2625-2651","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximation Algorithms for Covering Vertices by Long Paths"],"prefix":"10.1007","volume":"86","author":[{"given":"Mingyang","family":"Gong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brett","family":"Edgar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Fan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,5,28]]},"reference":[{"key":"1242_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/net.20200","volume":"50","author":"K Asdre","year":"2007","unstructured":"Asdre, K., Nikolopoulos, S.D.: A linear-time algorithm for the $$k$$-fixed-endpoint path cover problem on cographs. Networks 50, 231\u2013240 (2007)","journal-title":"Networks"},{"key":"1242_CR2","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1016\/j.tcs.2009.11.003","volume":"411","author":"K Asdre","year":"2010","unstructured":"Asdre, K., Nikolopoulos, S.D.: A polynomial solution to the $$k$$-fixed-endpoint path cover problem on proper interval graphs. Theor. Comput. Sci. 411, 967\u2013975 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"1242_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1,2)-TSP. In: Proceedings of the 17th ACM\u2013SIAM Annual Symposium on Discrete Algorithms (SODA 2006), pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"1242_CR4","doi-asserted-by":"crossref","unstructured":"Cai, Y., Chen, G., Chen, Y., Goebel, R., Lin, G., Liu, L., Zhang, A.: Approximation algorithms for two-machine flow-shop scheduling with a conflict graph. In: Proceedings of the 24th International Computing and Combinatorics Conference (COCOON 2018), LNCS 10976, pp. 205\u2013217 (2018)","DOI":"10.1007\/978-3-319-94776-1_18"},{"key":"1242_CR5","first-page":"66","volume":"6","author":"Y Chen","year":"2021","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. Combin. Optim. 6, 66 (2021)","journal-title":"J. Combin. Optim."},{"key":"1242_CR6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Z.-Z., Kennedy, C., Lin, G., Xu, Y., Zhang, A.: Approximation algorithms for the directed path partition problems. In: Proceedings of the 15th International Frontiers of Algorithmics Workshop (FAW 2021), LNCS 12874, pp. 23\u201336 (2021)","DOI":"10.1007\/978-3-030-97099-4_2"},{"key":"1242_CR7","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 the 13th International Frontiers of Algorithmics Workshop (FAW 2019), LNCS 11458, pp. 14\u201325 (2019)","DOI":"10.1007\/978-3-030-18126-0_2"},{"key":"1242_CR8","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. Combin. Optim. 38, 150\u2013164 (2019)","journal-title":"J. Combin. Optim."},{"key":"1242_CR9","unstructured":"Chen, Y., Goebel, R., Su, B., Tong, W., Xu, Y., Zhang, A.: A 21\/16-approximation for the minimum 3-path partition problem. In: The 30th Annual International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs 149, pp. 46:1\u201346:20 (2019)"},{"key":"1242_CR10","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"key":"1242_CR11","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 Company, San Francisco (1979)"},{"key":"1242_CR12","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. Combin. Optim. 39, 437\u2013456 (2020)","journal-title":"J. Combin. Optim."},{"key":"1242_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6, 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"key":"1242_CR14","doi-asserted-by":"crossref","unstructured":"Immorlica, N., Mahdian, M., Mirrokni, V.: Cycle cover with short cycles. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 641\u2013653 (2005)","DOI":"10.1007\/978-3-540-31856-9_53"},{"key":"1242_CR15","doi-asserted-by":"crossref","unstructured":"Kobayashi, K., Lin, G., Miyano, E., Saitoh, T., Suzuki, A., Utashima, T., Yagita, T.: Path cover problems with length cost. In: Proceedings of WALCOM 2022, LNCS 13174, pp. 396\u2013408 (2022)","DOI":"10.1007\/978-3-030-96731-4_32"},{"key":"1242_CR16","doi-asserted-by":"publisher","first-page":"3348","DOI":"10.1007\/s00453-023-01106-2","volume":"85","author":"K Kobayashi","year":"2023","unstructured":"Kobayashi, K., Lin, G., Miyano, E., Saitoh, T., Suzuki, A., Utashima, T., Yagita, T.: Path cover problems with length cost. Algorithmica 85, 3348\u20133375 (2023)","journal-title":"Algorithmica"},{"key":"1242_CR17","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. Oper. Res. Lett. 35, 677\u2013684 (2007)","journal-title":"Oper. Res. Lett."},{"key":"1242_CR18","unstructured":"Neuwohner, M.: An improved approximation algorithm for the maximum weight independent set problem in $$d$$-claw free graphs. In: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), LIPIcs 187, pp. 53:1\u201353:20 (2021)"},{"key":"1242_CR19","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.ipl.2007.12.006","volume":"107","author":"LL Pao","year":"2008","unstructured":"Pao, L.L., Hong, C.H.: The two-equal-disjoint path cover problem of matching composition network. Inf. Process. Lett. 107, 18\u201323 (2008)","journal-title":"Inf. Process. Lett."},{"key":"1242_CR20","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2105-15-S9-S5","volume":"15","author":"R Rizzi","year":"2014","unstructured":"Rizzi, R., Tomescu, A.I., M\u00e4kinen, V.: On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform. 15, S5 (2014)","journal-title":"BMC Bioinform."},{"key":"1242_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(97)00012-7","volume":"78","author":"J-H Yan","year":"1997","unstructured":"Yan, J.-H., Chang, G.J., Hedetniemi, S.M., Hedetniemi, S.T.: $$k$$-path partitions in trees. Discrete Appl. Math. 78, 227\u2013233 (1997)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01242-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01242-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01242-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T10:41:16Z","timestamp":1721904076000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01242-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,28]]},"references-count":21,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1242"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01242-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2561563\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,28]]},"assertion":[{"value":"7 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}