{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T05:11:33Z","timestamp":1656738693107},"reference-count":29,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2022,7,1]]},"DOI":"10.1587\/transinf.2021edp7177","type":"journal-article","created":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T22:18:40Z","timestamp":1656627520000},"page":"1258-1272","source":"Crossref","is-referenced-by-count":0,"title":["Reconfiguring &lt;i&gt;k&lt;\/i&gt;-Path Vertex Covers"],"prefix":"10.1587","volume":"E105.D","author":[{"given":"Duc A.","family":"HOANG","sequence":"first","affiliation":[{"name":"Kyoto University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"SUZUKI","sequence":"additional","affiliation":[{"name":"Tohoku University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsuyoshi","family":"YAGITA","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] D.A. Hoang, A. Suzuki, and T. Yagita, \u201cReconfiguring <i>k<\/i>-path vertex covers,\u201d Proc. WALCOM 2020, ed. M. Rahman, K. Sadakane, and W.K. Sung, LNCS, vol.12049, pp.133-145, Springer, 2020. 10.1007\/978-3-030-39881-1_12","DOI":"10.1007\/978-3-030-39881-1_12"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[3] N. Nishimura, \u201cIntroduction to reconfiguration,\u201d Algorithms, vol.11, no.4, 2018. (article 52). 10.3390\/a11040052","DOI":"10.3390\/a11040052"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[4] C. Mynhardt and S. Nasserasr, \u201cReconfiguration of colourings and dominating sets in graphs,\u201d in 50 years of Combinatorics, Graph Theory, and Computing, ed. F. Chung, R. Graham, F. Hoffman, R.C. Mullin, L. Hogben, and D.B. West, pp.171-191, CRC Press, 1st ed., 2019. 10.1201\/9780429280092-10","DOI":"10.1201\/9780429280092-10"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[5] M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman &amp; Co., New York, NY, USA, 1990. 10.1137\/1024022","DOI":"10.1137\/1024022"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[6] B. Bre\u0161ar, F. Kardo\u0161, J. Katreni\u010d, and G. Semani\u0161in, \u201cMinimum <i>k<\/i>-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","doi-asserted-by":"publisher","unstructured":"[7] H.B. Acharya, T. Choi, R.A. Bazzi, and M.G. Gouda, \u201cThe <i>k<\/i>-observer problem in computer networks,\u201d Netw. Sci., vol.1, no.1-4, pp.15-22, 2012. 10.1007\/s13119-011-0002-7","DOI":"10.1007\/s13119-011-0002-7"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[8] E. Miyano, T. Saitoh, R. Uehara, T. Yagita, and T.C. van der Zanden, \u201cComplexity of the maximum <i>k<\/i>-path vertex cover problem,\u201d Proc. WALCOM 2018, pp.240-251, Springer, 2018. 10.1007\/978-3-319-75172-6_21","DOI":"10.1007\/978-3-319-75172-6_21"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[9] B. Bre\u0161ar, R. Krivo\u0161-Bellu\u0161, G. Semani\u0161in, and P. \u0160parl, \u201cOn the weighted k-path vertex cover problem,\u201d Discrete Appl. Math., vol.177, pp.14-18, 2014. 10.1016\/j.dam.2014.05.042","DOI":"10.1016\/j.dam.2014.05.042"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[10] M. Kumar, A. Kumar, and C.P. Rangan, \u201cReoptimization of path vertex cover problem,\u201d Proc. COCOON 2019, LNCS, vol.11653, pp.363-374, Springer, 2019. 10.1007\/978-3-030-26176-4_30","DOI":"10.1007\/978-3-030-26176-4_30"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[11] Y. Ran, Z. Zhang, X. Huang, X. Li, and D.Z. Du, \u201cApproximation algorithms for minimum weight connected 3-path vertex cover,\u201d Appl. Math. Comput., vol.347, pp.723-733, 2019. 10.1016\/j.amc.2018.11.045","DOI":"10.1016\/j.amc.2018.11.045"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[12] D. Tsur, \u201cParameterized algorithm for 3-path vertex cover,\u201d Theor. Comput. Sci., vol.783, pp.1-8, 2019. 10.1016\/j.tcs.2019.03.013","DOI":"10.1016\/j.tcs.2019.03.013"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[13] M. Beck, K.Y. Lam, J.K.Y. Ng, S. Storandt, and C.J. Zhu, \u201cConcatenated <i>k<\/i>-path covers,\u201d Proc. ALENEX 2019, pp.81-91, 2019. 10.1137\/1.9781611975499.7","DOI":"10.1137\/1.9781611975499.7"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[14] S. Funke, A. Nusser, and S. Storandt, \u201cOn <i>k<\/i>-path covers and their applications,\u201d Proc. VLDB Endow., vol.7, no.10, pp.893-902, 2014. 10.14778\/2732951.2732963","DOI":"10.14778\/2732951.2732963"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[15] G. Ausiello, V. Bonifaci, and B. Escoffier, \u201cComplexity and approximation in reoptimization,\u201d in Computability in Context: Computation and Logic in the Real World, pp.101-129, World Scientific, 2011. 10.1142\/9781848162778_0004","DOI":"10.1142\/9781848162778_0004"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[16] T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, \u201cOn the complexity of reconfiguration problems,\u201d Theor. Comput. Sci., vol.412, no.12-14, pp.1054-1065, 2011. 10.1016\/j.tcs.2010.12.005","DOI":"10.1016\/j.tcs.2010.12.005"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] R.A. Hearn and E.D. Demaine, \u201cPSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation,\u201d Theor. Comput. Sci., vol.343, no.1-2, pp.72-96, 2005. 10.1016\/j.tcs.2005.05.008","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[18] T. Ito, M. Kami\u0144ski, H. Ono, A. Suzuki, R. Uehara, and K. Yamanaka, \u201cParameterized complexity of independent set reconfiguration problems,\u201d Discrete Applied Mathematics, vol.283,, pp.336-345, 2020. 10.1016\/j.dam.2020.01.022","DOI":"10.1016\/j.dam.2020.01.022"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[19] M. Kami\u0144ski, P. Medvedev, and M. Milani\u010d, \u201cComplexity of independent set reconfigurability problems,\u201d Theor. Comput. Sci., vol.439, pp.9-15, 2012. 10.1016\/j.tcs.2012.03.004","DOI":"10.1016\/j.tcs.2012.03.004"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[20] M. Wrochna, \u201cReconfiguration in bounded bandwidth and tree-depth,\u201d J. Comput. Syst. Sci., vol.93, pp.1-10, 2018. 10.1016\/j.jcss.2017.11.003","DOI":"10.1016\/j.jcss.2017.11.003"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] D. Lokshtanov and A.E. Mouawad, \u201cThe complexity of independent set reconfiguration on bipartite graphs,\u201d ACM Trans. Algorithms., vol.15, no.1, pp.7:1-7:19, 2019. 10.1145\/3280825","DOI":"10.1145\/3280825"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[22] R. Belmonte, E.J. Kim, M. Lampis, V. Mitsou, Y. Otachi, and F. Sikora, \u201cToken sliding on split graphs,\u201d Proc. STACS 2019, ed. R. Niedermeier and C. Paul, LIPIcs, vol.126, pp.13:1-13:7, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. 10.1007\/s00224-020-09967-8","DOI":"10.1007\/s00224-020-09967-8"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[23] E. Fox-Epstein, D.A. Hoang, Y. Otachi, and R. Uehara, \u201cSliding token on bipartite permutation graphs,\u201d Proc. ISAAC 2015, LNCS, vol.9472, pp.237-247, Springer, 2015. 10.1007\/978-3-662-48971-0_21","DOI":"10.1007\/978-3-662-48971-0_21"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[24] P. Bonsma, \u201cIndependent set reconfiguration in cographs and their generalizations,\u201d J. Graph Theory, vol.83, no.2, pp.164-195, 2016. 10.1002\/jgt.21992","DOI":"10.1002\/jgt.21992"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[25] P. Bonsma, M. Kami\u0144ski, and M. Wrochna, \u201cReconfiguring independent sets in claw-free graphs,\u201d Proc. SWAT 2014, LNCS, vol.8503, pp.86-97, Springer, 2014. 10.1007\/978-3-319-08404-6_8","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[26] M. Bonamy and N. Bousquet, \u201cToken sliding on chordal graphs,\u201d Proc. WG 2017, LNCS, vol.10520, pp.127-139, Springer, 2017. 10.1007\/978-3-319-68705-6_10","DOI":"10.1007\/978-3-319-68705-6_10"},{"key":"26","unstructured":"[27] M. Bria\u0144ski, S. Felsner, J. Hodor, and P. Micek, \u201cReconfiguring in-dependent sets on interval graphs,\u201d Proc. MFCS 2021, LIPIcs, vol.202, pp.23:1-23:14, 2021. 10.4230\/LIPIcs.MFCS.2021.23"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[28] E.D. Demaine, M.L. Demaine, E. Fox-Epstein, D.A. Hoang, T. Ito, H. Ono, Y. Otachi, R. Uehara, and T. Yamada, \u201cLinear-time algorithm for sliding tokens on trees,\u201d Theor. Comput. Sci., vol.600, pp.132-142, 2015. 10.1016\/j.tcs.2015.07.037","DOI":"10.1016\/j.tcs.2015.07.037"},{"key":"28","unstructured":"[29] T.C. van der Zanden, \u201cParameterized complexity of graph constraint logic,\u201d Proc. IPEC 2015, LIPIcs, vol.43, pp.282-293, 2015. 10.4230\/LIPIcs.IPEC.2015.282"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[30] R. Diestel, Graph Theory, 5th ed., Graduate Texts in Mathematics, vol.173, Springer, 2010. 10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-642-14279-6"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/7\/E105.D_2021EDP7177\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T04:41:03Z","timestamp":1656736863000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/7\/E105.D_2021EDP7177\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,1]]},"references-count":29,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2021edp7177","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,1]]},"article-number":"2021EDP7177"}}