{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:36Z","timestamp":1740109296471,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T00:00:00Z","timestamp":1590019200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T00:00:00Z","timestamp":1590019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"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\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971139","11771114","11571252"],"award-info":[{"award-number":["11971139","11771114","11571252"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["201908330090","201508330054"],"award-info":[{"award-number":["201908330090","201508330054"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan","award":["18K11183"],"award-info":[{"award-number":["18K11183"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00453-020-00717-3","type":"journal-article","created":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T01:02:35Z","timestamp":1590022955000},"page":"3041-3064","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs"],"prefix":"10.1007","volume":"82","author":[{"given":"An","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhi-Zhong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,21]]},"reference":[{"key":"717_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s13119-011-0002-7","volume":"1","author":"HB Acharya","year":"2012","unstructured":"Acharya, H.B., Choi, T., Bazzi, R.A., Gouda, M.G.: The $$k$$-observer problem in computer networks. Netw. Sci. 1, 15\u201322 (2012)","journal-title":"Netw. Sci."},{"key":"717_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237, 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"717_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for degree $$3$$ graphs. In: Proceedings of the Fourth International Workshop on Algorithms and Data Structures (WADS\u201995), LNCS 955, pp. 449\u2013460 (1995)","DOI":"10.1007\/3-540-60220-8_84"},{"key":"717_CR4","first-page":"241","volume":"72","author":"R Boliac","year":"2004","unstructured":"Boliac, R., Cameron, K., Lozin, V.: On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combinatoria 72, 241\u2013253 (2004)","journal-title":"Ars Combinatoria"},{"key":"717_CR5","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2014.05.042","volume":"177","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar, B., Krivo\u0161-Bellu\u0161, R., Semani\u0161in, G., \u0160parl, P.: On the weighted $$k$$-path vertex cover problem. Discrete Appl. Math. 177, 14\u201318 (2014)","journal-title":"Discrete Appl. Math."},{"key":"717_CR6","doi-asserted-by":"publisher","first-page":"1943","DOI":"10.1016\/j.dam.2013.02.024","volume":"161","author":"B Bre\u0161ar","year":"2013","unstructured":"Bre\u0161ar, B., Jakovac, M., Katreni\u010d, J., Semani\u0161in, G., Taranenko, A.: On the vertex $$k$$-path cover. Discrete Appl. Math. 161, 1943\u20131949 (2013)","journal-title":"Discrete Appl. Math."},{"key":"717_CR7","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. Discrete Appl. Math. 159, 1189\u20131195 (2011)","journal-title":"Discrete Appl. Math."},{"key":"717_CR8","unstructured":"Camby, E., Cardinal, J., Chapelle, M., Fiorini, S., Joret, G.: A primal-dual $$3$$-approximation algorithm for hitting $$4$$-vertex paths. In: The 9th International Colloquium on Graph Theory and Combinatorics (ICGT 2014), p.\u00a061 (2014)"},{"key":"717_CR9","first-page":"548","volume":"1997","author":"LJ Cowen","year":"1997","unstructured":"Cowen, L.J., Goddard, W., Jesurum, C.E.: Coloring with defects. Proc. SODA 1997, 548\u2013557 (1997)","journal-title":"Proc. SODA"},{"key":"717_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.dam.2014.10.033","volume":"184","author":"NS Devi","year":"2015","unstructured":"Devi, N.S., Mane, A.C., Mishra, S.: Computational complexity of minimum $$P_4$$ vertex cover problem for regular and $$K_{1,4}$$-free graphs. Discrete Appl. Math. 184, 114\u2013121 (2015)","journal-title":"Discrete Appl. Math."},{"key":"717_CR11","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0095-8956(85)90040-1","volume":"39","author":"O Favaron","year":"1985","unstructured":"Favaron, O.: On a conjecture of Fink and Jacobson concerning $$k$$-domination and $$k$$-dependence. J. Comb. Theory Series B 39, 101\u2013102 (1985)","journal-title":"J. Comb. Theory Series B"},{"key":"717_CR12","first-page":"159","volume":"250","author":"O Favaron","year":"1988","unstructured":"Favaron, O.: $$k$$-domination and $$k$$-dependence in graphs. Ars Combinatorics 250, 159\u2013167 (1988)","journal-title":"Ars Combinatorics"},{"key":"717_CR13","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":"717_CR14","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 329\u2013337 (2000)"},{"key":"717_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.dam.2015.02.018","volume":"187","author":"M Jakovac","year":"2015","unstructured":"Jakovac, M.: The $$k$$-path vertex cover of rooted product graphs. Discrete Appl. Math. 187, 111\u2013119 (2015)","journal-title":"Discrete Appl. Math."},{"key":"717_CR16","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.disc.2012.09.010","volume":"313","author":"M Jakovac","year":"2013","unstructured":"Jakovac, M., Taranenko, A.: On the $$k$$-path vertex cover of some graph products. Discrete Math. 313, 94\u2013100 (2013)","journal-title":"Discrete Math."},{"key":"717_CR17","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms 5, 41:1\u201341:8 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"717_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique $$2$$-prover $$1$$-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"717_CR19","unstructured":"Khot, S., Minzer, D., Safra, M.: Pseudorandom sets in Grassmann graph have near-perfect expansion. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pp. 592\u2013601 (2018)"},{"key":"717_CR20","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon$$. J. Comput. Syst. Sci. 74, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"717_CR21","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2014.01.019","volume":"526","author":"M Kumar","year":"2014","unstructured":"Kumar, M., Mishra, S., Devi, N.S., Saurabh, D.S.: Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization. Theor. Comput. Sci. 526, 90\u201396 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"717_CR22","first-page":"237","volume":"1","author":"L Lov\u00e1sz","year":"1966","unstructured":"Lov\u00e1sz, L.: On decompositions of graphs. Studia Scientiarum Mathematicarum Hungarica 1, 237\u2013238 (1966)","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"717_CR23","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","volume":"159","author":"Y Orlovich","year":"2011","unstructured":"Orlovich, Y., Dolgui, A., Finke, G., Gordond, V., Wernere, F.: The complexity of dissociation set problems in graphs. Discrete Appl. Math. 159, 1352\u20131366 (2011)","journal-title":"Discrete Appl. Math."},{"key":"717_CR24","doi-asserted-by":"crossref","unstructured":"Ries, B., Schamberg, B., Unger, W.: The $$k$$-observer problem on $$d$$-regular graphs. In: Stabilization, Safety, and Security of Distributed Systems (SSS 2015), LNCS 9212, pp. 81\u201393 (2015)","DOI":"10.1007\/978-3-319-21741-3_6"},{"key":"717_CR25","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.ipl.2013.04.002","volume":"113","author":"J Tu","year":"2013","unstructured":"Tu, J., Yang, F.: The vertex cover $$P_3$$ problem in cubic graphs. Inf. Process. Lett. 113, 481\u2013485 (2013)","journal-title":"Inf. Process. Lett."},{"key":"717_CR26","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"J Tu","year":"2011","unstructured":"Tu, J., Zhou, W.: A primal-dual approximation algorithm for the vertex cover $$P_3$$ problem. Theor. Comput. Sci. 412, 7044\u20137048 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"717_CR27","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00717-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00717-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00717-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T23:28:07Z","timestamp":1621553287000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00717-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,21]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["717"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00717-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,5,21]]},"assertion":[{"value":"23 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}