{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T09:53:12Z","timestamp":1769248392555,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s00453-023-01144-w","type":"journal-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T07:03:32Z","timestamp":1688713412000},"page":"505-525","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the d-Claw Vertex Deletion Problem"],"prefix":"10.1007","volume":"86","author":[{"given":"Sun-Yuan","family":"Hsieh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoang-Oanh","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9484-6677","authenticated-orcid":false,"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"1144_CR1","doi-asserted-by":"crossref","unstructured":"Bonomo-Braberman, F., Nascimento, J.R., Oliveira, F.S., Souza, U.S., Szwarcfiter, J.L.: Linear-time algorithms for eliminating claws in graphs. In: Computing and Combinatorics - 26th International Conference, COCOON: Proceedings, Lecture Notes in Computer Science, vol. 12273. Springer 2020, 14\u201326 (2020)","DOI":"10.1007\/978-3-030-58150-3_2"},{"key":"1144_CR2","doi-asserted-by":"crossref","unstructured":"Bonomo-Braberman, F., Nascimento, J.R., Oliveira, F.S., Souza, U.S., Szwarcfiter, J.L.: Linear-time algorithms for eliminating claws in graphs. Int. Trans. Op.er Res. 0, 1\u201320 (2021)","DOI":"10.1111\/itor.13100"},{"issue":"2","key":"1144_CR3","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"key":"1144_CR4","unstructured":"Cao, Y., Ke, Y., Otachi, Y., You, J.: Vertex deletion problems on chordal graphs. In: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, LIPIcs, vol.\u00a093, pp.\u00a022:1\u201322:14 (2017)"},{"key":"1144_CR5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2018.05.039","volume":"745","author":"Y Cao","year":"2018","unstructured":"Cao, Y., Ke, Y., Otachi, Y., You, J.: Vertex deletion problems on chordal graphs. Theor. Comput. Sci. 745, 75\u201386 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"1144_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.disopt.2015.11.003","volume":"19","author":"M-S Chang","year":"2016","unstructured":"Chang, M.-S., Chen, L.-H., Hung, L.-J., Rossmanith, P., Ping-Chen, S.: Fixed-parameter algorithms for vertex cover p$${}_{\\text{3 }}$$. Discrete Optim. 19, 12\u201322 (2016)","journal-title":"Discrete Optim."},{"issue":"40\u201342","key":"1144_CR7","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"1144_CR8","unstructured":"Crespelle, C., Drange, P.G., Fomin, F.V., Golovach, P.A.: A survey of parameterized algorithms and the complexity of edge modification. arXiv:2001.06867 (2020)"},{"key":"1144_CR9","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Joret, G., Schaudt, O.: Improved approximation algorithms for hitting 3-vertex paths. Math. Program. 182(1\u20132), 355\u2013367 (2020)","DOI":"10.1007\/s10107-019-01395-y"},{"key":"1144_CR10","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"3","key":"1144_CR11","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/16M1070670","volume":"31","author":"V Guruswami","year":"2017","unstructured":"Guruswami, V., Lee, E.: Inapproximability of h-transversal\/packing. SIAM J. Discrete Math. 31(3), 1552\u20131571 (2017)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"1144_CR12","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"JD Horton","year":"1993","unstructured":"Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6(3), 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"1144_CR13","doi-asserted-by":"crossref","unstructured":"Hsieh, S.-Y., Le, V.B., Peng, S.L.: On the d-claw vertex deletion problem. In: Computing and Combinatorics - 27th International Conference, COCOON: Tainan, Taiwan, October 24\u201326, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13025. Springer 2021, pp. 591\u2013603 (2021)","DOI":"10.1007\/978-3-030-89543-3_49"},{"key":"1144_CR14","doi-asserted-by":"crossref","unstructured":"Jena, S.K., Subramani, K.: Analyzing the 3-path vertex cover problem in planar bipartite graphs. In: Theory and Applications of Models of Computation - 17th Annual Conference, TAMC 2022, Tianjin, China, September 16\u201318, 2022, Proceedings (Du, D.-Z., Du, D., Wu, C., Xu, D. eds.), Lecture Notes in Computer Science, vol. 13571, Springer, pp.\u00a0103\u2013115 (2022)","DOI":"10.1007\/978-3-031-20350-3_10"},{"issue":"3","key":"1144_CR15","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(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"1144_CR16","doi-asserted-by":"crossref","unstructured":"Kumar, M., Mishra, S., Devi, N.S., Saurabh, S.: Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization. Theor. Comput. Sci. 526, 90\u201396 (2014)","DOI":"10.1016\/j.tcs.2014.01.019"},{"key":"1144_CR17","unstructured":"Le, H.-O., Le, V.B.: Complexity of the cluster vertex deletion problem on H-free graphs. In: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22\u201326, 2022, Vienna, Austria (Szeider, S., Ganian, R., Silva, A., eds.), LIPIcs, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a068:1\u201368:10 (2022)"},{"key":"1144_CR18","doi-asserted-by":"crossref","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"1144_CR19","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"1144_CR20","doi-asserted-by":"crossref","unstructured":"Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Automata, Languages and Programming, 20nd International Colloquium, ICALP93, Lecture Notes in Computer Science, vol. 700, Springer, pp.\u00a040\u201351 (1993)","DOI":"10.1007\/3-540-56939-1_60"},{"key":"1144_CR21","doi-asserted-by":"crossref","unstructured":"Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573\u2013590 (2001)","DOI":"10.1007\/s00454-001-0047-6"},{"key":"1144_CR22","doi-asserted-by":"crossref","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is np-hard. J. ACM 55(2), 11:1\u201311:29 (2008)","DOI":"10.1145\/1346330.1346336"},{"key":"1144_CR23","doi-asserted-by":"crossref","unstructured":"Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35(2), 167\u2013170 (1992)","DOI":"10.1016\/0166-218X(92)90041-8"},{"key":"1144_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.03.013","volume":"783","author":"D Tsur","year":"2019","unstructured":"Tsur, D.: Parameterized algorithm for 3-path vertex cover. Theor. Comput. Sci. 783, 1\u20138 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1144_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00224-020-10005-w","volume":"65","author":"D Tsur","year":"2021","unstructured":"Tsur, D.: Faster parameterized algorithm for cluster vertex deletion. Theor. Comput. Syst. 65(2), 323\u2013343 (2021)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"1144_CR26","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(2), 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-023-01144-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01144-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01144-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T09:10:24Z","timestamp":1706087424000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01144-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1144"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01144-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"31 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}