{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:26Z","timestamp":1759638446648},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_52","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"613-624","source":"Crossref","is-referenced-by-count":19,"title":["Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions"],"prefix":"10.1007","author":[{"given":"Eun Jung","family":"Kim","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Langer","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for Dominating Set. Journal of the ACM\u00a051, 363\u2013384 (2004)","journal-title":"Journal of the ACM"},{"key":"52_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 105\u2013118. Springer, Heidelberg (1988)"},{"key":"52_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"52_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: Proc. of 50th FOCS, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"issue":"2","key":"52_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Information and Computation\u00a0167(2), 86\u2013119 (2001)","journal-title":"Information and Computation"},{"issue":"7","key":"52_CR6","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a074(7), 1188\u20131198 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"52_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-17493-3_11","volume-title":"Parameterized and Exact Computation","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 95\u2013106. Springer, Heidelberg (2010)"},{"key":"52_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/11533719_87","volume-title":"Computing and Combinatorics","author":"F. Dehne","year":"2005","unstructured":"Dehne, F., Fellows, M., Langston, M.A., Rosamond, F., Stevens, K.: An O(2\n                    O(k)\n                  n\n                  3) FPT algorithm for the undirected feedback vertex set problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 859\u2013869. Springer, Heidelberg (2005)"},{"key":"52_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R. Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"issue":"11","key":"52_CR10","first-page":"1199","volume":"3","author":"M. Dinneen","year":"1997","unstructured":"Dinneen, M.: Too many minor order obstructions. Journal of Universal Computer Science\u00a03(11), 1199\u20131206 (1997)","journal-title":"Journal of Universal Computer Science"},{"key":"52_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM\u00a035, 727\u2013739 (1988)","journal-title":"Journal of the ACM"},{"key":"52_CR13","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: Approximation and kernelization. In: STACS 28th. LIPIcs, vol.\u00a09, pp. 189\u2013200. Schloss Dagstuhl\u2013Leibniz-Zentrum fu (2011)\u0308r Informatik (2011)"},{"key":"52_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \n                    \n                      \n                    \n                    $\\mathcal{F}$\n                  -Deletion: Approximation and Optimal FPT Algorithms. In: Proc. of 53rd FOCS, pp. 470\u2013479. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. of 21st SODA, pp. 503\u2013510. SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"issue":"7","key":"52_CR16","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1016\/j.ejc.2010.05.003","volume":"31","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Oum, S., Thilikos, D.M.: Rank-width and tree-width of H-minor-free graphs. European Journal of Combinatorics\u00a031(7), 1617\u20131628 (2010)","journal-title":"European Journal of Combinatorics"},{"issue":"8","key":"52_CR17","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a072(8), 1386\u20131396 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"52_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"key":"52_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-23719-5_34","volume-title":"Algorithms \u2013 ESA 2011","author":"G. Joret","year":"2011","unstructured":"Joret, G., Paul, C., Sau, I., Saurabh, S., Thomass\u00e9, S.: Hitting and harvesting pumpkins. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 394\u2013407. Springer, Heidelberg (2011)"},{"key":"52_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-31155-0_11","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"E.J. Kim","year":"2012","unstructured":"Kim, E.J., Paul, C., Philip, G.: A single-exponential FPT-algorithm for K\n                  4-minor cover problem. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 119\u2013130. Springer, Heidelberg (2012)"},{"key":"52_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-642-10217-2_37","volume-title":"Combinatorial Algorithms","author":"D. Lokshtanov","year":"2009","unstructured":"Lokshtanov, D., Saurabh, S., Sikdar, S.: Simpler parameterized algorithm for OCT. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol.\u00a05874, pp. 380\u2013384. Springer, Heidelberg (2009)"},{"key":"52_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-16926-7_19","volume-title":"Graph Theoretic Concepts in Computer Science","author":"G. Philip","year":"2010","unstructured":"Philip, G., Raman, V., Villanger, Y.: A quartic kernel for Pathwidth-One Vertex Deletion. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 196\u2013207. Springer, Heidelberg (2010)"},{"key":"52_CR23","doi-asserted-by":"publisher","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\u00a0II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"52_CR24","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors\u00a0XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"52_CR25","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A. Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. Journal of Combinatorial Theory, Series B\u00a081(2), 318\u2013338 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:42:40Z","timestamp":1558302160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}