{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:11Z","timestamp":1759638611847,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,5,3]],"date-time":"2017-05-03T00:00:00Z","timestamp":1493769600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152","648527"],"award-info":[{"award-number":["280152","648527"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-017-0316-2","type":"journal-article","created":{"date-parts":[[2017,5,3]],"date-time":"2017-05-03T09:55:16Z","timestamp":1493805316000},"page":"251-270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Polynomial Kernel for Block Graph Deletion"],"prefix":"10.1007","volume":"79","author":[{"given":"Eun Jung","family":"Kim","sequence":"first","affiliation":[]},{"given":"O-Joung","family":"Kwon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,3]]},"reference":[{"key":"316_CR1","first-page":"1","volume-title":"A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion","author":"A Agrawal","year":"2016","unstructured":"Agrawal, A., Kolay, S., Lokshtanov, D., Saurabh, S.: A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion, pp. 1\u201313. Springer, Berlin (2016)"},{"key":"316_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Lokshtanov, D., Misra, P., Saurabh, S., Zehavi, M.: Feedback vertex set inspired kernel for chordal vertex deletion. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp. 1383\u20131398. Society for Industrial and Applied Mathematics, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.90"},{"key":"316_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: On disjoint cycles. In: Proceedings of the 17th International Workshop, WG \u201991, pp. 230\u2013238. Springer, London (1992)","DOI":"10.1007\/3-540-55121-2_24"},{"key":"316_CR4","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O., Marx, D.: Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property, pp. 233\u2013244. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53536-3_20"},{"key":"316_CR5","doi-asserted-by":"crossref","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: New measure and new structures. Algorithmica 73(1), 63\u201386 (2015)","DOI":"10.1007\/s00453-014-9904-6"},{"issue":"1","key":"316_CR6","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/s00453-015-0014-x","volume":"75","author":"Y Cao","year":"2016","unstructured":"Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. Algorithmica 75(1), 118\u2013137 (2016)","journal-title":"Algorithmica"},{"issue":"7","key":"316_CR7","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"316_CR8","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"316_CR9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-642-17493-3_11","volume-title":"Parameterized and Exact Computation. Lecture Notes in Computer Science","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.: An improved fpt algorithm and quadratic kernel for pathwidth one vertex deletion. In: Raman, V., Saurabh, S. (eds.) Parameterized and Exact Computation. Lecture Notes in Computer Science, pp. 95\u2013106. Springer, Berlin (2010)"},{"key":"316_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2011, pp. 150\u2013159. IEEE Computer Society, Los Alamitos (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"316_CR11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discret. Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"316_CR12","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F Dehne","year":"2007","unstructured":"Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An $${O}(2^{O(k)}n^3)$$ O ( 2 O ( k ) n 3 ) fpt algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"316_CR13","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. III. Some structural aspects of the W hierarchy. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 191\u2013225. Cambridge University Press, Cambridge (1993)"},{"key":"316_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, 20\u201323 Oct 2012, pp. 470\u2013479 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"316_CR15","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02066678","volume":"12","author":"T Gallai","year":"1961","unstructured":"Gallai, T.: Maximum-minimum S\u00e4tze und verallgemeinerte Faktoren von Graphen. Acta Math. Acad. Sci. Hungar. 12, 131\u2013173 (1961)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"issue":"8","key":"316_CR16","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"316_CR17","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"key":"316_CR18","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Pilipczuk, M.: Approximation and kernelization for chordal vertex deletion. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp. 1399\u20131418. Society for Industrial and Applied Mathematics, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.91"},{"key":"316_CR19","unstructured":"Kim, E.J., Kwon, O.: A Polynomial Kernel for Block Graph Deletion. In: Husfeldt, T., Kanj, I. (eds.) 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 43, pp. 270\u2013281. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2015)"},{"key":"316_CR20","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-540-28639-4_21","volume-title":"Parameterized and Exact Computation. Lecture Notes in Computer Science","author":"I Kanj","year":"2004","unstructured":"Kanj, I., Pelsmajer, M., Schaefer, M.: Parameterized algorithms for feedback vertex set. In: Downey, R., Fellows, M., Dehne, F. (eds.) Parameterized and Exact Computation. Lecture Notes in Computer Science, pp. 235\u2013247. Springer, Berlin (2004)"},{"key":"316_CR21","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):Art. 21, 41 (2016)","DOI":"10.1145\/2797140"},{"issue":"10","key":"316_CR22","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"key":"316_CR23","doi-asserted-by":"crossref","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized independent feedback vertex set. Theor. Comput. Sci. 461(0):65\u201375 (2012). 17th International Computing and Combinatorics Conference (COCOON 2011)","DOI":"10.1016\/j.tcs.2012.02.012"},{"issue":"1","key":"316_CR24","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"316_CR25","doi-asserted-by":"crossref","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) Algorithms and Computation, Volume 2518 of Lecture Notes in Computer Science, pp. 241\u2013248. Springer, Berlin (2002)","DOI":"10.1007\/3-540-36136-7_22"},{"issue":"4","key":"316_CR26","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"316_CR27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"316_CR28","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9.","year":"2010","unstructured":"Thomass\u00e9., S.: A $$4{k}^2$$ 4 k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0316-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0316-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0316-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,22]],"date-time":"2019-09-22T23:38:49Z","timestamp":1569195529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0316-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["316"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0316-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,5,3]]}}}