{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:27:35Z","timestamp":1743049655908,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319751719"},{"type":"electronic","value":"9783319751726"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-75172-6_21","type":"book-chapter","created":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T11:23:02Z","timestamp":1517311382000},"page":"240-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of the Maximum k-Path Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Eiji","family":"Miyano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiki","family":"Saitoh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsuyoshi","family":"Yagita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom C.","family":"van der Zanden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,31]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Dis. Appl. Math. 165, 37\u201348 (2014)","journal-title":"Dis. Appl. Math."},{"key":"21_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. Dis. Optim. 3, 220\u2013229 (2006)","journal-title":"Dis. Optim."},{"issue":"6","key":"21_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"L Hans","year":"1996","unstructured":"Hans, L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $${O}(c^k n)$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"21_CR5","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. Dis. Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Dis. Appl. Math."},{"key":"21_CR6","unstructured":"Camby, E.: Connecting hitting sets and hitting paths in graphs. Ph.D. thesis, Doctoral Thesis (2015)"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. In: IFIP International Conference on Theoretical Computer Science, pp. 13\u201326. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-44602-7_2"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol. B, pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Compleixty of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"21_CR11","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2015.12.002","volume":"116","author":"J Katreni\u010d","year":"2016","unstructured":"Katreni\u010d, J.: A faster FPT algorithm for 3-path vertex cover. Inf. Process. Lett. 116(4), 273\u2013278 (2016)","journal-title":"Inf. Process. Lett."},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.dam.2015.12.004","volume":"205","author":"X Li","year":"2016","unstructured":"Li, X., Zhang, Z., Huang, X.: Approximation algorithms for minimum (weight) connected k-path vertex cover. Dis. Appl. Math. 205, 101\u2013108 (2016)","journal-title":"Dis. Appl. Math."},{"issue":"2","key":"21_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285\u2013309 (1982)","journal-title":"J. ACM"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.dam.2015.06.032","volume":"200","author":"T Jianhua","year":"2016","unstructured":"Jianhua, T., Jin, Z.: An FPT algorithm for the vertex cover P4 problem. Dis. Appl. Math. 200, 186\u2013190 (2016)","journal-title":"Dis. Appl. Math."},{"issue":"14","key":"21_CR15","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"T Jianhua","year":"2011","unstructured":"Jianhua, T., Zhou, W.: A factor 2 approximation algorithm for the vertex cover P3 problem. Inf. Process. Lett. 111(14), 683\u2013686 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"50","key":"21_CR16","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"T Jianhua","year":"2011","unstructured":"Jianhua, T., Zhou, W.: A primal-dual approximation algorithm for the vertex cover P3 problem. Theor. Comput. Sci. 412(50), 7044\u20137048 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2016.04.043","volume":"657","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Kou, S.: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theor. Comput. Sci. 657, 86\u201397 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10, 310\u2013327 (1981)","journal-title":"SIAM J. Comput."},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ipl.2016.11.003","volume":"119","author":"Z Zhang","year":"2017","unstructured":"Zhang, Z., Li, X., Shi, Y., Nie, H., Zhu, Y.: PTAS for minimum k-path vertex cover in ball graph. Inf. Process. Lett. 119, 9\u201313 (2017)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-75172-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:40:47Z","timestamp":1710344447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-75172-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319751719","9783319751726"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-75172-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"31 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dhaka","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bangladesh","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 March 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 March 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cse.buet.ac.bd\/walcom2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}