{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:10:20Z","timestamp":1774635020665,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":78,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642283314","type":"print"},{"value":"9783642283321","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_4","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T14:45:36Z","timestamp":1330526736000},"page":"38-56","source":"Crossref","is-referenced-by-count":2,"title":["A Parameterized Complexity Tutorial"],"prefix":"10.1007","author":[{"given":"Rod","family":"Downey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/3-540-56503-5_38","volume-title":"STACS 93","author":"K. Abrahamson","year":"1993","unstructured":"Abrahamson, K., Downey, R., Fellows, M.: Fixed-Parameter Intractability II. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol.\u00a0665, pp. 374\u2013385. Springer, Heidelberg (1993)"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K. Abrahamson","year":"1995","unstructured":"Abrahamson, K., Downey, R., Fellows, M.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic\u00a073, 235\u2013276 (1995), http:\/\/www.mrfellows.net\/papers\/J31-fpt4-95.pdf","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theory Comput. Syst.\u00a041(3), 411\u2013430 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","volume":"45","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for FPT problems. Algorithmica\u00a045(3), 269\u2013284 (2006)","journal-title":"Algorithmica"},{"key":"4_CR5","unstructured":"Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 641\u2013650. SIAM (2008)"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Resolution is not automatizable unless W[P] is tractable. In: FOCS, pp. 210\u2013219. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959895"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Proc. Symp. Theory of Computing (STOC), pp. 326\u2013335. ACM (1994)","DOI":"10.1145\/195058.195179"},{"key":"4_CR8","unstructured":"Bazgan, C.: Sch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e, Rapport de stage de DEA d\u2019Informatique \u00e0 Orsay. Tech. rep., Informatique d\u2019Orsay (1995)"},{"key":"4_CR9","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":"4_CR10","first-page":"49","volume":"11","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R., Fellows, M., Hallett, M.T., Wareham, H.T.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011, 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"issue":"8","key":"4_CR11","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R., Fellows, M., Hermelin, D.: On problems without polynomial kernels. Journal of Computing and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"Journal of Computing and System Sciences"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: FOCS, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. The Computer Journal\u00a051, 255\u2013269 (2008)","journal-title":"The Computer Journal"},{"key":"4_CR14","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Analysis of data reduction, transformations give evidence for non-existence of polynomial kernels. Tech. Rep. UU-CS-2008-030, Utrecht University (2008)"},{"issue":"4","key":"4_CR15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R., Fellows, M.: On the parameterized complexity of short computation and factorization. Arch. for Math. Logic\u00a036, 321\u2013337 (1997)","journal-title":"Arch. for Math. Logic"},{"key":"4_CR17","first-page":"459","volume":"41","author":"L. Cai","year":"2007","unstructured":"Cai, L., Fellows, M., Juedes, D.W., Rosamond, F.A.: The complexity of polynomial-time approximation. Theoretical Computer Science\u00a041, 459\u2013477 (2007)","journal-title":"Theoretical Computer Science"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-48224-5_23","volume-title":"Automata, Languages and Programming","author":"L. Cai","year":"2001","unstructured":"Cai, L., Juedes, D.W.: Subexponential Parameterized Algorithms Collapse the W-Hierarchy. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 273\u2013284. Springer, Heidelberg (2001)"},{"key":"4_CR19","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.W.: On the existence of subexponential parameterized algorithms. Journal of Computing and Systems Science\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computing and Systems Science"},{"issue":"4","key":"4_CR20","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J. Cheetham","year":"2003","unstructured":"Cheetham, J., Dehne, F.K.H.A., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse-grained parallel machines. Journal of Computer and Systems Sciences\u00a067(4), 691\u2013706 (2003)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201, 216\u2013231 (2005)","journal-title":"Information and Computation"},{"key":"4_CR22","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.\u00a0411, 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"4_CR23","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/s00224-010-9270-y","volume":"48","author":"Y. Chen","year":"2011","unstructured":"Chen, Y., Flum, J., M\u00fcller, M.: Lower bounds for kernelizations and other preprocessing procedures. Theory Comput. Syst.\u00a048(4), 803\u2013839 (2011)","journal-title":"Theory Comput. Syst."},{"key":"4_CR24","unstructured":"Courcelle, B.: Recognizability and second-order definability for sets of finite graphs. Tech. Rep. I-8634, Universite de Bordeaux (1987)"},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J.\u00a051(3), 292\u2013302 (2008)","journal-title":"Comput. J."},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Downey, R.: Parameterized complexity for the skeptic. In: Proc. 18th IEEE Annual Conference on Computational Complexity, pp. 147\u2013169 (2003)","DOI":"10.1109\/CCC.2003.1214417"},{"key":"4_CR27","unstructured":"Downey, R., Fellows, M.: Fixed parameter tractability and completeness. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory: Current Research, pp. 161\u2013187. Cambridge University Press (1992); congressus Numerantium, 87"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Fixed-parameter intractability. In: Structure in Complexity Theory Conference, pp. 36\u201349 (1992)","DOI":"10.1109\/SCT.1992.215379"},{"key":"4_CR29","first-page":"166","volume-title":"Complexity Theory: Current Research - Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity","author":"R. Downey","year":"1993","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: Current Research - Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity, pp. 166\u2013191. Cambridge University Press, Cambridge (1993)"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness I: Basic theory. SIAM Journal of Computing\u00a024, 873\u2013921 (1995), http:\/\/mrfellows.net\/papers\/J29-completeness1-95.ps","journal-title":"SIAM Journal of Computing"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness II: Completeness for W[1]. Theoretical Computer Science A\u00a0141, 109\u2013131 (1995), http:\/\/mrfellows.net\/papers\/J30-CompletenessII-95.ps","journal-title":"Theoretical Computer Science A"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Proceedings of the Second Cornell Workshop on Feasible Mathematics. Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995), http:\/\/mrfellows.net\/papers\/C17-feasibility95.ps","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"4_CR33","first-page":"530","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1998","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity, 530 pages. Springer, Heidelberg (1998)"},{"key":"4_CR34","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer, Heidelberg (in preparation, 2012)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"4_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-58140-5_10","volume-title":"Logical Foundations of Computer Science","author":"R. Downey","year":"1994","unstructured":"Downey, R., Fellows, M., Kapron, B., Hallett, M., Wareham, H.T.: The Parameterized Complexity of Some Problems in Logic and Linguistics. In: Matiyasevich, Y.V., Nerode, A. (eds.) LFCS 1994. LNCS, vol.\u00a0813, pp. 89\u2013100. Springer, Heidelberg (1994)"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Langston, M.: Two Special Issue of The Computer Journal Special Issue on Parameterized Complexity. The Computer Journal 51(1 and 3) (2008), http:\/\/mrfellows.net\/papers\/J71-Jforward08.pdf","DOI":"10.1093\/comjnl\/bxm111"},{"issue":"1","key":"4_CR37","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"R. Downey","year":"2008","unstructured":"Downey, R., Fellows, M., McCartin, C., Rosamond, F.: Parameterized approximation of dominating set problems. Information Processing Letters\u00a0109(1), 68\u201370 (2008)","journal-title":"Information Processing Letters"},{"issue":"1-2","key":"4_CR38","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00317-9","volume":"191","author":"R. Downey","year":"1998","unstructured":"Downey, R., Fellows, M., Regan, K.W.: Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science A\u00a0191(1-2), 97\u2013115 (1998), http:\/\/mrfellows.net\/papers\/DFR98_CircuitComplexity.pdf","journal-title":"Theoretical Computer Science A"},{"key":"4_CR39","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.cosrev.2011.09.002","volume":"5","author":"R. Downey","year":"2011","unstructured":"Downey, R., Thilikos, D.M.: Confronting intractability via parameters. Computer Science Review\u00a05, 279\u2013317 (2011)","journal-title":"Computer Science Review"},{"key":"4_CR40","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canad. J. Math.\u00a017, 449\u2013467 (1965), http:\/\/www.cs.berkeley.edu\/~christos\/classics\/edmonds.ps","journal-title":"Canad. J. Math."},{"key":"4_CR41","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/CCC.2008.24","volume-title":"Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, CCC 2008","author":"K. Eickmeyer","year":"2008","unstructured":"Eickmeyer, K., Grohe, M., Gr\u00fcber, M.: Approximation of natural W[P]-Complete minimisation problems is hard. In: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, CCC 2008, pp. 8\u201318. IEEE Computer Society, Washington, DC (2008), http:\/\/dx.doi.org\/10.1109\/CCC.2008.24"},{"issue":"3","key":"4_CR42","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M. Fellows","year":"1987","unstructured":"Fellows, M., Langston, M.A.: Nonconstructive advances in polynomial-time complexity. Information Processing Letters\u00a026(3), 155\u2013162 (1987)","journal-title":"Information Processing Letters"},{"issue":"3","key":"4_CR43","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M. Fellows","year":"1988","unstructured":"Fellows, M., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. Journal of the Association for Computing Machinery\u00a035(3), 727\u2013739 (1988)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"4_CR44","doi-asserted-by":"crossref","unstructured":"Fellows, M., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 520\u2013525. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"key":"4_CR45","unstructured":"de Fluiter, B.: Algorithms for graphs of small treewidth. Ph.D. thesis, Utrecht University (1970)"},{"key":"4_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/3-540-45841-7_29","volume-title":"STACS 2002","author":"J. Flum","year":"2002","unstructured":"Flum, J., Grohe, M.: Describing Parameterized Complexity Classes. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 359\u2013371. Springer, Heidelberg (2002)"},{"key":"4_CR47","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 538\u2013547. IEEE Computer Society (2002)","DOI":"10.1109\/SFCS.2002.1181978"},{"key":"4_CR48","first-page":"71","volume":"84","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: Parametrized complexity and subexponential time. Bulletin of the EATCS\u00a084, 71\u2013100 (2004)","journal-title":"Bulletin of the EATCS"},{"key":"4_CR49","series-title":"Texts in theoretical computer science","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Texts in theoretical computer science. Springer, Heidelberg (2006), http:\/\/books.google.com\/books?id=VfJz6hvFAjoC"},{"issue":"1","key":"4_CR50","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. Journal of Computing and System Sciences\u00a077(1), 91\u2013106 (2011)","journal-title":"Journal of Computing and System Sciences"},{"issue":"6","key":"4_CR51","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM\u00a048(6), 1184\u20131206 (2001), http:\/\/doi.acm.org\/10.1145\/504794.504798","journal-title":"J. ACM"},{"key":"4_CR52","first-page":"215","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, LICS 2002","author":"M. Frick","year":"2002","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, LICS 2002, pp. 215\u2013224. IEEE Computer Society, Washington, DC (2002)"},{"key":"4_CR53","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"4_CR54","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1993","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. Journal of Computational Biology\u00a02(1), 139\u2013152 (1993)","journal-title":"Journal of Computational Biology"},{"key":"4_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-45678-3_38","volume-title":"Algorithms and Computation","author":"J. Gramm","year":"2001","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Exact Solutions for Closest String and Related Problems. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 441\u2013453. Springer, Heidelberg (2001)"},{"key":"4_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-44693-1_2","volume-title":"STACS 2001","author":"M. Grohe","year":"2001","unstructured":"Grohe, M.: Generalized Model-Checking Problems for First-Order Logic. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 12\u201326. Springer, Heidelberg (2001)"},{"key":"4_CR57","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Grohe, M., Makowsky, J. (eds.) Model Theoretic Methods in Finite Combinatorics. Contemporary Mathematics, vol.\u00a0558. American Mathematical Society (2011)","DOI":"10.1090\/conm\/558"},{"issue":"3","key":"4_CR58","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s00224-007-1329-z","volume":"41","author":"M. Hallett","year":"2007","unstructured":"Hallett, M., Mccartin, C.: A faster FPT algorithm for the maximum agreement forest problem. Theory of Computing Systems\u00a041(3), 539\u2013550 (2007)","journal-title":"Theory of Computing Systems"},{"key":"4_CR59","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Whalstrom, M., Wu, X.: Hierarchies of inefficient kernelization (to appear)"},{"issue":"4","key":"4_CR60","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(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR61","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"4_CR62","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jcss.2010.06.009","volume":"77","author":"R. Karp","year":"2011","unstructured":"Karp, R.: Heuristic algorithms in computational molecular biology. Journal of Computer and System Sciences\u00a077(1), 122\u2013128 (2011), http:\/\/dx.doi.org\/10.1016\/j.jcss.2010.06.009","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"4_CR63","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science\u00a0289(2), 997\u20131008 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR64","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1093\/comjnl\/bxm003","volume":"51","author":"M.A. Langston","year":"2008","unstructured":"Langston, M.A., Perkins, A.D., Saxton, A.M., Scharff, J.A., Voy, B.H.: Innovative computational methods for transcriptomic data analysis: A case study in the use of FPT for practical algorithm design and implementation. The Computer Journal\u00a051(1), 26\u201338 (2008)","journal-title":"The Computer Journal"},{"issue":"2","key":"4_CR65","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. Journal Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"Journal Algorithms"},{"key":"4_CR66","doi-asserted-by":"crossref","unstructured":"Marx, D.: Future directions in parameterized complexity (tentative title) (to appear, 2012)","DOI":"10.1007\/978-3-642-30891-8_20"},{"issue":"1-3","key":"4_CR67","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.apal.2005.06.010","volume":"138","author":"C. McCartin","year":"2006","unstructured":"McCartin, C.: Parameterized counting problems. Annals of Pure and Applied Logic\u00a0138(1-3), 147\u2013182 (2006)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/11847250_5","volume-title":"Parameterized and Exact Computation","author":"M. M\u00fcller","year":"2006","unstructured":"M\u00fcller, M.: Randomized Approximations of Parameterized Counting Problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 50\u201359. Springer, Heidelberg (2006)"},{"key":"4_CR69","unstructured":"M\u00fcller, M.: Valiant-Vazirani Lemmata for various logics. Electronic Colloquium on Computational Complexity (ECCC)\u00a015(063) (2008)"},{"key":"4_CR70","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter Jr., L.: Vertex packings: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"4_CR71","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Habilitationschrift, University of T\u00fcbingen (2002)"},{"key":"4_CR72","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications. Oxford University Press (2006), http:\/\/books.google.com\/books?id=mAA_OkeJxhsC","DOI":"10.1093\/acprof:oso\/9780198566076.003.0001"},{"key":"4_CR73","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters\u00a073, 125\u2013129 (2000), http:\/\/theinf1.informatik.uni-jena.de\/publications\/ipl00.pdf","journal-title":"Information Processing Letters"},{"key":"#cr-split#-4_CR74.1","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. In: PODS, pp. 12-19. ACM Press (1997)","DOI":"10.1145\/263661.263664"},{"key":"#cr-split#-4_CR74.2","doi-asserted-by":"crossref","unstructured":"Journal Version in Journal of Computer System Sciences 58, 407-427 (1999)","DOI":"10.1006\/jcss.1999.1626"},{"issue":"4","key":"4_CR75","doi-asserted-by":"publisher","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. Operations Research Letters\u00a032(4), 299\u2013301 (2004), http:\/\/dx.doi.org\/10.1016\/j.orl.2003.10.009","journal-title":"Operations Research Letters"},{"issue":"3","key":"4_CR76","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. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"4_CR77","series-title":"CRPIT","first-page":"25","volume-title":"Australasian Symposium on Parallel and Distributed Computing (AusPDC 2011)","author":"D.P. Weerapurage","year":"2011","unstructured":"Weerapurage, D.P., Eblen, J.D., Rogers, G., Langston, M.A.: Parallel Vertex Cover: A Case Study in Dynamic Load Balancing. In: Chen, J., Ranjan, R. (eds.) Australasian Symposium on Parallel and Distributed Computing (AusPDC 2011). CRPIT, vol.\u00a0118, pp. 25\u201332. ACS, Perth (2011), http:\/\/crpit.com\/confpapers\/CRPITV118Weerapurage.pdf"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T06:20:10Z","timestamp":1742624410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":78,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}