{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T16:38:58Z","timestamp":1648917538567},"reference-count":20,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2020,10,1]]},"DOI":"10.1587\/transfun.2019dmp0014","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T22:23:00Z","timestamp":1601504580000},"page":"1193-1201","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of the Maximum &lt;i&gt;k&lt;\/i&gt;-Path Vertex Cover Problem"],"prefix":"10.1587","volume":"E103.A","author":[{"given":"Eiji","family":"MIYANO","sequence":"first","affiliation":[{"name":"Kyushu Institute of Technology"}]},{"given":"Toshiki","family":"SAITOH","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology"}]},{"given":"Ryuhei","family":"UEHARA","sequence":"additional","affiliation":[{"name":"Japan Advanced Institute of Science and Technology"}]},{"given":"Tsuyoshi","family":"YAGITA","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology"}]},{"given":"Tom C. van der","family":"ZANDEN","sequence":"additional","affiliation":[{"name":"Maastricht University"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] N. Apollonio and B. Simeone, \u201cThe maximum vertex coverage problem on bipartite graphs,\u201d Discrete Appl. Math., vol.165, pp.37-48, 2014. 10.1016\/j.dam.2013.05.015","DOI":"10.1016\/j.dam.2013.05.015"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] N. Betzler, R. Niedermeier, and J. Uhlmann, \u201cTree decompositions of graphs: Saving memory in dynamic programming,\u201d Discrete Optim., vol.3, no.3, pp.220-229, 2006. 10.1016\/j.disopt.2006.05.008","DOI":"10.1016\/j.disopt.2006.05.008"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] H.L. Bodlaender, \u201cA linear-time algorithm for finding tree-decompositions of small treewidth,\u201d SIAM J. Comput., vol.25, no.6, pp.1305-1317, 1996. 10.1137\/s0097539793251219","DOI":"10.1137\/S0097539793251219"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] H.L. Bodlaender, P.G. Drange, M.S. Dregi, F.V. Fomin, D. Lokshtanov, and M. Pilipczuk, \u201cA <i>O<\/i>(<i>c<sup>k<\/sup>n<\/i>) 5-approximation algorithm for treewidth,\u201d SIAM J. Comput., vol.45, no.2, pp.317-378, 2016. 10.1137\/130947374","DOI":"10.1137\/130947374"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] B. Bre\u0161ar, F. Kardo\u0161, J. Katreni\u010d, and G. Semani\u0161in, \u201cMinimum k-path vertex cover,\u201d Discrete Appl. Math., vol.159, no.12, pp.1189-1195, 2011. 10.1016\/j.dam.2011.04.008","DOI":"10.1016\/j.dam.2011.04.008"},{"key":"6","unstructured":"[6] E. Camby, Connecting Hitting Sets and Hitting Paths in Graphs, PhD thesis, Doctoral Thesis, 2015."},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] B. Caskurlu, V. Mkrtchyan, O. Parekh, and K. Subramani, \u201cOn partial vertex cover and budgeted maximum coverage problems in bipartite graphs,\u201d IFIP Inte. Conf. on Theoretical Computer Science, pp.13-26, Springer, 2014. 10.1007\/978-3-662-44602-7_2","DOI":"10.1007\/978-3-662-44602-7_2"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] B. Courcelle, \u201cGraph rewriting: An algebraic and logic approach,\u201d Handbook of Theoretical Computer Science, vol.B, pp.193-242, 1990. 10.1016\/b978-0-444-88074-1.50010-x","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] N.S. Devi, A.C. Mane, and S. Mishra, \u201cComputational complexity of minimum P4 vertex cover problem for regular and K1,4-free graphs,\u201d Discrete Appl. Math., vol.184, pp.114-121, 2015. 10.1016\/j.dam.2014.10.033","DOI":"10.1016\/j.dam.2014.10.033"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] T.F. Gonzalez, \u201cClustering to minimize the maximum intercluster distance,\u201d Theor. Comput. Sci., vol.38, pp.293-306, 1985. 10.1016\/0304-3975(85)90224-5","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[12] J. Katreni\u010d, \u201cA faster FPT algorithm for 3-path vertex cover,\u201d Inf. Process. Lett., vol.116, no.4, pp.273-278, 2016. 10.1016\/j.ipl.2015.12.002","DOI":"10.1016\/j.ipl.2015.12.002"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[13] X. Li, Z. Zhang, and X. Huang, \u201cApproximation algorithms for minimum (weight) connected k-path vertex cover,\u201d Discrete Appl. Math., vol.205, pp.101-108, 2016. 10.1016\/j.dam.2015.12.004","DOI":"10.1016\/j.dam.2015.12.004"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[14] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, and F. Werner, \u201cOn the complexity of dissociation set problems in graphs,\u201d IFAC Proceedings Volumes, vol.42, no.4, pp.1032-1036, 2009. 10.3182\/20090603-3-ru-2001.0071","DOI":"10.3182\/20090603-3-RU-2001.0071"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[15] C.H. Papadimitriou and M. Yannakakis, \u201cThe complexity of restricted spanning tree problems,\u201d J. ACM, vol.29, no.2, pp.285-309, 1982. 10.1145\/322307.322309","DOI":"10.1145\/322307.322309"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[16] J. Tu and Z. Jin, \u201cAn FPT algorithm for the vertex cover P4 problem,\u201d Discrete Appl. Math., vol.200, pp.186-190, 2016. 10.1016\/j.dam.2015.06.032","DOI":"10.1016\/j.dam.2015.06.032"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] J. Tu and W. Zhou, \u201cA factor 2 approximation algorithm for the vertex cover P3 problem,\u201d Inf. Process. Lett., vol.111, no.14, pp.683-686, 2011. 10.1016\/j.ipl.2011.04.009","DOI":"10.1016\/j.ipl.2011.04.009"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[18] J. Tu and W. Zhou, \u201cA primal-dual approximation algorithm for the vertex cover P3 problem,\u201d Theor. Comput. Sci., vol.412, no.50, pp.7044-7048, 2011. 10.1016\/j.tcs.2011.09.013","DOI":"10.1016\/j.tcs.2011.09.013"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[19] M. Xiao and S. Kou, \u201cExact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems,\u201d Theor. Comput. Sci., vol.657, pp.86-97, 2017. 10.1016\/j.tcs.2016.04.043","DOI":"10.1016\/j.tcs.2016.04.043"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[20] M. Yannakakis, \u201cNode-deletion problems on bipartite graphs,\u201d SIAM J. Comput., vol.10, no.2, pp.310-327, 1981. 10.1137\/0210022","DOI":"10.1137\/0210022"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] Z. Zhang, X. Li, Y. Shi, H. Nie, and Y. Zhu, \u201cPTAS for minimum k-path vertex cover in ball graph,\u201d Inf. Process. Lett., vol.119, pp.9-13, 2017. 10.1016\/j.ipl.2016.11.003","DOI":"10.1016\/j.ipl.2016.11.003"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E103.A\/10\/E103.A_2019DMP0014\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T03:37:30Z","timestamp":1601696250000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E103.A\/10\/E103.A_2019DMP0014\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,1]]},"references-count":20,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2019dmp0014","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,1]]}}}