{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:01:17Z","timestamp":1743066077906,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031630200"},{"type":"electronic","value":"9783031630217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_24","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:02:29Z","timestamp":1718974949000},"page":"314-326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Directed Path Partition Problem on\u00a0Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Eto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Kawaharada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tugce","family":"Ozdemir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105150","volume":"297","author":"Y Chen","year":"2024","unstructured":"Chen, Y., Chen, Z.Z., Kennedy, C., Lin, G., Xu, Y., Zhang, A.: Approximating the directed path partition problem. Inf. Comput. 297, 105150 (2024). https:\/\/doi.org\/10.1016\/j.ic.2024.105150","journal-title":"Inf. Comput."},{"issue":"5","key":"24_CR2","doi-asserted-by":"publisher","first-page":"3595","DOI":"10.1007\/S10878-022-00915-5","volume":"44","author":"Y Chen","year":"2022","unstructured":"Chen, Y., et al.: A local search 4\/3-approximation algorithm for the minimum 3-path partition problem. J. Comb. Optim. 44(5), 3595\u20133610 (2022). https:\/\/doi.org\/10.1007\/S10878-022-00915-5","journal-title":"J. Comb. Optim."},{"key":"24_CR3","doi-asserted-by":"publisher","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: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol.\u00a0149, pp. 46:1\u201346:20. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.46","DOI":"10.4230\/LIPIcs.ISAAC.2019.46"},{"key":"24_CR4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009). http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"24_CR5","unstructured":"Erickson, J.: Algorithms (2019). http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/"},{"key":"24_CR6","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, New York (1979)"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/S10107-004-0505-Z","volume":"100","author":"AV Goldberg","year":"2004","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100(3), 537\u2013568 (2004). https:\/\/doi.org\/10.1007\/S10107-004-0505-Z","journal-title":"Math. Program."},{"issue":"19\u201320","key":"24_CR8","doi-asserted-by":"publisher","first-page":"2498","DOI":"10.1016\/J.DISC.2005.12.039","volume":"306","author":"IB Hartman","year":"2006","unstructured":"Hartman, I.B.: Berge\u2019s conjecture on directed path partitions - a survey. Discret. Math. 306(19\u201320), 2498\u20132514 (2006). https:\/\/doi.org\/10.1016\/J.DISC.2005.12.039","journal-title":"Discret. Math."},{"issue":"4","key":"24_CR9","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001). https:\/\/doi.org\/10.1145\/502090.502098","journal-title":"J. ACM"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/J.ENDM.2018.05.009","volume":"67","author":"N Korpelainen","year":"2018","unstructured":"Korpelainen, N.: A boundary class for the k-path partition problem. Electron. Notes Discret. Math. 67, 49\u201356 (2018). https:\/\/doi.org\/10.1016\/J.ENDM.2018.05.009","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"24_CR11","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). https:\/\/doi.org\/10.1137\/0211025","journal-title":"SIAM J. Comput."},{"issue":"3","key":"24_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0012-365X(78)90007-9","volume":"23","author":"N Linial","year":"1978","unstructured":"Linial, N.: Covering digraphs by paths. Discret. Math. 23(3), 257\u2013272 (1978). https:\/\/doi.org\/10.1016\/0012-365X(78)90007-9","journal-title":"Discret. Math."},{"key":"24_CR13","doi-asserted-by":"publisher","unstructured":"Manuel, P.: Revisiting path-type covering and partitioning problems. arXiv:1807.10613 (2018). https:\/\/doi.org\/10.48550\/arXiv.1807.10613","DOI":"10.48550\/arXiv.1807.10613"},{"issue":"5","key":"24_CR14","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(5), 677\u2013684 (2007). https:\/\/doi.org\/10.1016\/J.ORL.2006.12.004","journal-title":"Oper. Res. Lett."},{"issue":"1\u20133","key":"24_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(97)00012-7","volume":"78","author":"J Yan","year":"1997","unstructured":"Yan, J., Chang, G.J., Hedetniemi, S.M., Hedetniemi, S.T.: k-path partitions in trees. Discret. Appl. Math. 78(1\u20133), 227\u2013233 (1997). https:\/\/doi.org\/10.1016\/S0166-218X(97)00012-7","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:15:31Z","timestamp":1718975731000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}