{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T23:07:37Z","timestamp":1786144057861,"version":"3.56.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734192","type":"print"},{"value":"9783540734208","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_4","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"15-27","source":"Crossref","is-referenced-by-count":5,"title":["Subexponential Parameterized Algorithms"],"prefix":"10.1007","author":[{"given":"Frederic","family":"Dorn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Alber","year":"2000","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Niedermeier, R.: Fixed parameter algorithms for planar dominating set and related problems. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 97\u2013110. Springer, Heidelberg (2000)"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-44683-4_11","volume-title":"Mathematical Foundations of Computer Science 2001","author":"J. Alber","year":"2001","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F.A., Stege, U.: Refined search tree technique for dominating set on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 111\u2013122. Springer, Heidelberg (2001)"},{"key":"4_CR4","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":"4_CR5","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms\u00a052, 26\u201356 (2004)","journal-title":"J. Algorithms"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H. Bodlaender","year":"2007","unstructured":"Bodlaender, H.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, Springer, Heidelberg (2007) (to appear)"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. System Sci.\u00a067, 789\u2013807 (2003)","journal-title":"J. Comput. System Sci."},{"key":"4_CR8","series-title":"Lecture Notes in Artificial Intelligence","first-page":"269","volume-title":"Formal Concept Analysis","author":"J. Chen","year":"2005","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. In: Ganter, B., Godin, R. (eds.) ICFCA 2005. LNCS (LNAI), vol.\u00a03403, pp. 269\u2013280. Springer, Heidelberg (2005)"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/j.orl.2005.04.013","volume":"34","author":"V.G. De\u01d0eko","year":"2006","unstructured":"De\u01d0eko, V.G., Klinz, B., Woeginger, G.J.: Exact algorithms for the Hamiltonian cycle problem in planar graphs. Oper. Res. Lett. 34, 269\u2013274 (2006)","journal-title":"Oper. Res. Lett."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Math.\u00a018, 501\u2013511 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms\u00a01, 33\u201347 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. Journal of the ACM\u00a052, 866\u2013893 (2005)","journal-title":"Journal of the ACM"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica (to appear)","DOI":"10.1007\/s00493-008-2140-4"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Computer Journal (to appear)","DOI":"10.1093\/comjnl\/bxm033"},{"key":"4_CR15","first-page":"590","volume-title":"SODA 2005","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: SODA 2005, pp. 590\u2013601. ACM-SIAM, New York (2005)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. System Sci.\u00a069, 166\u2013195 (2004)","journal-title":"J. Comput. System Sci."},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica\u00a041, 245\u2013267 (2005)","journal-title":"Algorithmica"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/040616929","volume":"20","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discrete Math.\u00a020, 357\u2013371 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/11785293_18","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 172\u2013183. Springer, Heidelberg (2006)"},{"key":"4_CR21","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming on H-minor-free graphs, manuscript (2007)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"4_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/1060590.1060674","volume-title":"STOC 2005","author":"U. Feige","year":"2005","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: STOC 2005, pp. 563\u2013572. ACM Press, New York (2005)"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 1\u201312. Springer, Heidelberg (2003)"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/978-3-540-28629-5_37","volume-title":"Mathematical Foundations of Computer Science 2004","author":"H. Fernau","year":"2004","unstructured":"Fernau, H., Juedes, D.W.: A geometric approach to parameterized algorithms for domination problems on planar graphs. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 488\u2013499. Springer, Heidelberg (2004)"},{"key":"4_CR27","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1007\/978-3-540-27836-8_50","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 581\u2013592. Springer, Heidelberg (2004)"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput.\u00a036, 281\u2013309 (2006)","journal-title":"SIAM J. Comput."},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory\u00a051, 53\u201381 (2006)","journal-title":"Journal of Graph Theory"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica\u00a023, 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"4_CR32","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.jcss.2005.02.003","volume":"71","author":"G. Gutin","year":"2005","unstructured":"Gutin, G., Kloks, T., Lee, C.M., Yeo, A.: Kernels in planar digraphs. J. Comput. System Sci.\u00a071, 174\u2013184 (2005)","journal-title":"J. Comput. System Sci."},{"key":"4_CR33","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Computer and System Sciences\u00a063, 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/3-540-45687-2_33","volume-title":"Mathematical Foundations of Computer Science 2002","author":"I. Kanj","year":"2002","unstructured":"Kanj, I., Perkovi\u0107, L.: Improved parameterized algorithms for planar dominating set. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 399\u2013410. Springer, Heidelberg (2002)"},{"key":"4_CR35","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press, Oxford (2006)"},{"key":"4_CR36","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N.: Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B\u00a089, 43\u201376 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"4_CR37","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B\u00a062, 323\u2013348 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"4_CR38","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014, 217\u2013241 (1994)","journal-title":"Combinatorica"}],"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-540-73420-8_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:11:09Z","timestamp":1619518269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}