{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:47:19Z","timestamp":1743094039069,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":82,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781461411673"},{"type":"electronic","value":"9781461411680"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-1-4614-1168-0_13","type":"book-chapter","created":{"date-parts":[[2011,12,2]],"date-time":"2011-12-02T05:18:38Z","timestamp":1322803118000},"page":"269-293","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Multivariate Complexity Theory"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,10,22]]},"reference":[{"key":"13_CR100_13","doi-asserted-by":"crossref","unstructured":"K. Abrahamson, J. Ellis, M. Fellows and M. Mata (1989). On the complexity of fixed-parameter problems. FOCS 1989, 210\u2013215.","DOI":"10.1109\/SFCS.1989.63480"},{"key":"13_CR2_13","doi-asserted-by":"crossref","unstructured":"S. Arnborg, A. Proskurowski, D. Seese (1990). Monadic Second Order Logic, Tree Automata and Forbidden Minors. CSL 1990,1\u201316.","DOI":"10.1007\/3-540-54487-9_49"},{"key":"13_CR3_13","unstructured":"C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, C.-G. Quimper, and T. Walsh (2008). The parameterized complexity of global constraints. AAAI 2008, 235\u2013240."},{"issue":"45","key":"13_CR4_13","doi-asserted-by":"publisher","first-page":"4554","DOI":"10.1016\/j.tcs.2009.08.033","volume":"410","author":"N Betzler","year":"2009","unstructured":"N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier, and F. A. Rosamond (2009). Fixed-parameter algorithms for Kemeny rankings. Theoretical Computer Science 410(45), 4554\u20134570.","journal-title":"Theoretical Computer Science"},{"key":"13_CR5_13","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender (1988). Dynamic programming on graphs with bounded treewidth. ICALP 1988, 105\u2013118.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"13_CR6_13","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. STOC 1993: 226\u2013234.","DOI":"10.1145\/167088.167161"},{"issue":"8","key":"13_CR7_13","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin (2009). On problems without polynomial kernels. Journal of Computer and System Sciences 75(8), 423\u2013434.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4\/5","key":"13_CR8_13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L Cai","year":"1997","unstructured":"L. Cai, J. Chen, R. G. Downey, and M. R. Fellows (1997). The parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36(4\/5), 321\u2013337.","journal-title":"Archive for Mathematical Logic"},{"issue":"3","key":"13_CR9_13","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1093\/comjnl\/bxm035","volume":"51","author":"L Cai","year":"2008","unstructured":"L. Cai, X. Huang, C. Liu, F. Rosamond, and Y. Song (2008). Parameterized complexity and biopolymer sequence comparison. The Computer Journal 51(3), 270\u2013291.","journal-title":"The Computer Journal"},{"issue":"4","key":"13_CR10_13","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"L. Cai and D. Juedes (2003). On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences 67(4), 789\u2013807.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR11_13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S1571-0661(04)81019-3","volume":"78","author":"M-C Cai","year":"2003","unstructured":"M-C. Cai, X. Deng (2003). Approximation and computation of arbitrage in frictional foreign exchange market (extended abstract). Electronic Notes in Theoretical Computer Science 78, 293\u2013302.","journal-title":"Electronic Notes in Theoretical Computer Science"},{"issue":"4","key":"13_CR12_13","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J Cheetham","year":"2003","unstructured":"J. Cheetham, F. Dehne, A. Rau-Chaplin, U. Stege, and P. J. Taillon (2003). Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences 67(4), 691\u2013706.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"13_CR13_13","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes, I. Kanj, and G. Xia (2005). Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201(2), 216\u2013231.","journal-title":"Information and Computation"},{"key":"13_CR14_13","doi-asserted-by":"crossref","unstructured":"J. Chen, X. Huang, I. Kanj, and G. Xia (2004). Linear FPT reductions and computational lower bounds. STOC 2004, 212\u2013221.","DOI":"10.1145\/1007352.1007391"},{"key":"13_CR15_13","doi-asserted-by":"crossref","unstructured":"J. Chen, I. A. Kanj, and G. Xia (2006). Improved parameterized upper bounds for Vertex Cover. MFCS 2006, 238\u2013249.","DOI":"10.1007\/11821069_21"},{"key":"13_CR16_13","doi-asserted-by":"crossref","unstructured":"J. Chen, Y. Liu, S. Lu, B. O\u2019Sullivan, and I. Razgon (2008). A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM 55(5).","DOI":"10.1145\/1411509.1411511"},{"issue":"1","key":"13_CR17_13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1093\/comjnl\/bxm036","volume":"51","author":"J Chen","year":"2008","unstructured":"J. Chen and J. Meng (2008). On parameterized intractability: hardness and completeness. The Computer Journal 51(1), 39\u201359.","journal-title":"The Computer Journal"},{"key":"13_CR18_13","doi-asserted-by":"crossref","unstructured":"B. Chor, M. R. Fellows, and D. W. Juedes (2004). Linear kernels in linear time, or how to save k colors in O(n) steps. WG 2004, 257\u2013269.","DOI":"10.1007\/978-3-540-30559-0_22"},{"key":"13_CR19_13","unstructured":"The Computer Journal (2008). Two special issues of surveys of various aspects of parameterized complexity and algorithmics (Guest Editors: M. Fellows, R. Downey and M. Langston). The Computer Journal, Volume 51: Number 1 and Number 3."},{"issue":"1","key":"13_CR20_13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"B. Courcelle (1990) The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs Inf. Comput. 85(1): 12\u201375.","journal-title":"Inf. Comput."},{"key":"13_CR21_13","doi-asserted-by":"crossref","unstructured":"H. Dell and D. van Melkebeek (2010). Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC 2010, 251\u2013260.","DOI":"10.1145\/1806689.1806725"},{"key":"13_CR22_13","doi-asserted-by":"crossref","unstructured":"E. Demaine (2001). Playing games with algorithms: algorithmic combinatorial game theory. MFCS 2001, 18\u201332.","DOI":"10.1007\/3-540-44683-4_3"},{"issue":"3","key":"13_CR23_13","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E Demaine","year":"2008","unstructured":"E. Demaine and M. T. Hajiaghayi (2008). The bidimensionality theory and its algorithmic applications. The Computer Journal 51(3), 292\u2013302.","journal-title":"The Computer Journal"},{"key":"13_CR24_13","doi-asserted-by":"crossref","unstructured":"Discrete Optimization (2011). Special issue on parameterized complexity of discrete optimization (Guest Editors: M. R. Fellows, F. V. Fomin, and G. Gutin) 8(1).","DOI":"10.1016\/j.disopt.2011.02.001"},{"key":"13_CR26_13","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows (1995a). Fixed-parameter tractability and completeness I: basic results. SIAM Journal on Computing 24, 873\u2013921.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR27_13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows (1995b). Fixed-parameter tractability and completeness II: on completeness for W[1]. Theoretical Computer Science 141, 109\u2013131.","journal-title":"Theoretical Computer Science"},{"key":"13_CR28_13","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows (1998). Parameterized Complexity. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"13_CR29_13","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows, B. Kapron, M. T. Hallett, and H. T. Wareham (1994). Parameterized complexity of some problems in logic and linguistics. LFCS 1994, 89\u2013100.","DOI":"10.1007\/3-540-58140-5_10"},{"key":"13_CR30_13","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows, and C. McCartin (2006). Parameterized approximation algorithms. IWPEC 2006, 121\u2013129.","DOI":"10.1007\/11847250_11"},{"key":"13_CR32_13","unstructured":"R. G. Downey, M. Fellows, and U. Taylor (1997). The parameterized complexity of relational database queries and an improved characterization of W[1]. DMTCS 1996, 194\u2013213."},{"key":"13_CR34_13","doi-asserted-by":"crossref","unstructured":"M. Fellows (2002). Parameterized complexity: the main ideas and connections to practical computing. In: Experimental Algorithmics, Springer-Verlag, 51\u201377.","DOI":"10.1007\/3-540-36383-1_3"},{"key":"13_CR35_13","doi-asserted-by":"crossref","unstructured":"M. R. Fellows (2003). Blow-ups, win\/win\u2019s and crown rules: some new directions in FPT. WG 2003, 1\u201312.","DOI":"10.1007\/978-3-540-39890-5_1"},{"key":"13_CR36_13","doi-asserted-by":"crossref","unstructured":"M. R. Fellows (2009). Towards fully multivariate algorithmics: some new results and directions in parameter ecology. IWOCA 2009, 2\u201310.","DOI":"10.1007\/978-3-642-10217-2_2"},{"issue":"2","key":"13_CR37_13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen (2011). On the complexity of some colorful problems parameterized by treewidth. Information and Computation 209(2), 143\u2013153.","journal-title":"Information and Computation"},{"issue":"1","key":"13_CR38_13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette (2009a). Theoretical Computer Science 410(1), 53\u201361.","journal-title":"Theoretical Computer Science"},{"key":"13_CR39_13","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and N. Koblitz (1993). Fixed-parameter complexity and cryptography. AAECC 1993, 121\u2013131.","DOI":"10.1007\/3-540-56686-4_38"},{"key":"13_CR40_13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"MR Fellows","year":"1987","unstructured":"M. R. Fellows and M. Langston (1987). Nonconstructive advances in polynomial time complexity. Information Processing Letters 26, 157\u2013162.","journal-title":"Information Processing Letters"},{"key":"13_CR41_13","doi-asserted-by":"crossref","unstructured":"M. Fellows, M. A. Langston. (1989a) On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract) STOC 1989, 501\u2013512.","DOI":"10.1145\/73007.73055"},{"key":"13_CR42_13","doi-asserted-by":"crossref","unstructured":"M. Fellows, M.A. Langston(1989b) An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract) FOCS 1989: 520\u2013525.","DOI":"10.1109\/SFCS.1989.63528"},{"key":"13_CR43_13","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and F. Rosamond (2007). The complexity ecology of parameters: an illustration using bounded max leaf number. CiE 2007, 268\u2013277.","DOI":"10.1007\/978-3-540-73001-9_28"},{"key":"13_CR44_13","unstructured":"M. R. Fellows, F. A. Rosamond, F. V. Fomin, D. Lokshtanov, S. Saurabh, and Y. Villanger (2009b). Local search: is brute-force avoidable? IJCAI 2009, 486\u2013491."},{"key":"13_CR45_13","unstructured":"H. Fernau, T. Hagerup, N. Nishimura, P. Ragde and K. Reinhardt (2003). On the parameterized complexity of the generalized rush hour puzzle. CCCG 2003, 6\u20139."},{"key":"13_CR46_13","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh (2010). Fast local search algorithm for Weighted Feedback Arc Set in Tournaments. AAAI 2010.","DOI":"10.1609\/aaai.v24i1.7557"},{"key":"13_CR47_13","unstructured":"J. Flum and M. Grohe (2006). Parameterized Complexity Theory, Springer-Verlag."},{"key":"13_CR48_13","unstructured":"S. Gaspers, D. Kratsch, and M. Liedloff. On independent sets and bicliques in graphs. Algorithmica, to appear."},{"key":"13_CR49_13","unstructured":"S. Gaspers and S. Szeider (2011). Kernels for global constraints. IJCAI 2011, to appear."},{"issue":"3","key":"13_CR50_13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/comjnl\/bxm056","volume":"51","author":"G Gottlob","year":"2008","unstructured":"G. Gottlob and S. Szeider (2008). Fixed-parameter algorithms for Artificial Intelligence, Constraint Satisfaction and Database Problems. The Computer Journal 51(3), 303\u2013325.","journal-title":"The Computer Journal"},{"key":"13_CR52_13","doi-asserted-by":"crossref","unstructured":"M. Grohe (2002). The parameterized complexity of database queries. PODS 2002, 82\u201392.","DOI":"10.1145\/375551.375564"},{"key":"13_CR54_13","doi-asserted-by":"crossref","unstructured":"J. Guo, H. Moser, and R. Niedermeier (2009). Iterative compression for exactly solving NP-hard minimization problems. Algorithmics of Large and Complex Networks 2009, 65\u201380.","DOI":"10.1007\/978-3-642-02094-0_4"},{"key":"13_CR55_13","doi-asserted-by":"crossref","unstructured":"J. Guo and R. Niedermeier (2007). Invitation to data reduction and problem kernelization. SIGACT News, March 2007, 31\u201345.","DOI":"10.1145\/1233481.1233493"},{"key":"13_CR104_13","doi-asserted-by":"crossref","unstructured":"S. Hartung and R. Niedermeier (2010). Incremental list coloring of graphs, parameterized by conservation. TAMC 2010, 258\u2013270.","DOI":"10.1007\/978-3-642-13562-0_24"},{"key":"13_CR56_13","doi-asserted-by":"crossref","unstructured":"S. Helwig, F. H\u00fcffner, I. R\u00f6ssling, and M. Weinard (2010). Selected design issues. Algorithm Engineering 2010, 58\u2013126.","DOI":"10.1007\/978-3-642-14866-8_3"},{"key":"13_CR57_13","doi-asserted-by":"crossref","unstructured":"F. Henglein and H. G. Mairson (1991). The complexity of type inference for higher-order typed lambda calculi. POPL 1991, 119\u2013130.","DOI":"10.1145\/99583.99602"},{"issue":"2","key":"13_CR58_13","doi-asserted-by":"crossref","first-page":"77","DOI":"10.7155\/jgaa.00177","volume":"13","author":"F H\u00fcffner","year":"2009","unstructured":"F. H\u00fcffner (2009). Algorithm engineering for optimal graph bipartization. Journal of Graph Algorithms and Applications 13(2), 77\u201398.","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"1","key":"13_CR59_13","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1093\/comjnl\/bxm040","volume":"51","author":"F H\u00fcffner","year":"2008","unstructured":"F. H\u00fcffner, R. Niedermeier, and S. Wernicke (2008). Techniques for practical fixed-parameter algorithms. The Computer Journal, 51(1):7\u201325.","journal-title":"The Computer Journal"},{"key":"13_CR60_13","unstructured":"Journal of Computer and System Sciences (2003). Parameterized computation and complexity. (Guest Editors: Jianer Chen, Michael R. Fellows ), 67(4)."},{"issue":"3","key":"13_CR61_13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"S. Khot and O. Regev (2008). Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. Journal of Computer and System Sciences 74(3), 335\u2013349.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR62_13","doi-asserted-by":"crossref","unstructured":"C. Komusiewicz, R. Niedermeier, and J. Uhlmann (2009). Deconstructing intractability a case study for interval constrained coloring. CPM 2009, 207\u2013220.","DOI":"10.1007\/978-3-642-02441-2_19"},{"key":"13_CR64_13","unstructured":"M. A. Langston, F. N. Abu-Khzam, R. L. Collins, M. R. Fellows, W. H. Suters, and C. T. Symons (2004). Kernelization algorithms for the Vertex Cover problem: theory and experiments. ALENEX 2004, 62\u201369."},{"key":"13_CR65_13","unstructured":"M. A. Langston, F. N. Abu-Khzam, and P. Shanbhag (2003). Scalable parallel algorithms for difficult combinatorial problems: a case study in optimization. PDCS 2003, 649\u2013654."},{"key":"13_CR66_13","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein and A. Pneuli (1985). Checking that finite-state concurrent programs satisfy their linear specification. POPL 1985, 97\u2013107.","DOI":"10.1145\/318593.318622"},{"issue":"2","key":"13_CR67_13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"M. Mahajan and V. Raman (1999). Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms 31(2), 335\u2013354.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"13_CR68_13","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"D. Marx (2008a). Parameterized complexity and approximation algorithms. The Computer Journal 51(1), 60\u201378.","journal-title":"The Computer Journal"},{"issue":"1","key":"13_CR103_13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.orl.2007.02.008","volume":"36","author":"D. Marx","year":"2008b","unstructured":"D. Marx (2008b). Searching the k-change neighborhood for TSP is W[1]-hard. Operations Research Letters 36(1), 31\u201336.","journal-title":"Operations Research Letters"},{"key":"13_CR69_13","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn (1984). Data Structures and Efficient Algorithms, Volume 2: Graph Algorithms and NP-Completeness, Springer.","DOI":"10.1007\/978-3-642-69897-2"},{"issue":"1","key":"13_CR70_13","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.disopt.2010.10.001","volume":"8","author":"N Misra","year":"2011","unstructured":"N. Misra, V. Raman, and S. Saurabh (2011). Lower bounds on kernelization. Discrete Optimization 8(1), 110\u2013128.","journal-title":"Discrete Optimization"},{"key":"13_CR72_13","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and L. E. Trotter (1975). Vertex packings: structural properties and algorithms. Mathematical Programming 8, 232\u2013248.","journal-title":"Mathematical Programming"},{"key":"13_CR73_13","doi-asserted-by":"crossref","unstructured":"R. Niedermeier (2006). Invitation to Fixed Parameter Algorithms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"13_CR74_13","unstructured":"R. Niedermeier (2010). Reflections on multivariate algorithmics and problem parameterization. STACS 2010, 17\u201332."},{"key":"13_CR75_13","unstructured":"S. Ordyniak, D. Paulusma, and S. Szeider (2010). Satisfiability of acyclic and almost acyclic CNF formulas. FSTTCS 2010, 84\u201395."},{"key":"13_CR76_13","doi-asserted-by":"crossref","unstructured":"S.-I. Oum (2005). Approximating rank-width and cliquewidth quickly. WG 2005, 49\u201358.","DOI":"10.1007\/11604686_5"},{"key":"13_CR77_13","unstructured":"C. Papadimitriou and M. Yannakakis (1997). On the complexity of database queries. POPL 1997, 12\u201319."},{"issue":"12","key":"13_CR80_13","doi-asserted-by":"publisher","first-page":"e14067","DOI":"10.1371\/journal.pone.0014067","volume":"5","author":"R Rizzi","year":"2010","unstructured":"R. Rizzi, P. Mahata, L. Mathieson, and P. Moscato (2010). Hierarchical clustering using the arithmetic-harmonic cut: complexity and experiments. PLoS ONE 5(12): e14067.","journal-title":"PLoS ONE"},{"issue":"1","key":"13_CR81_13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"N. Robertson and P. D. Seymour (1983) Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B 35(1), 39\u201361.","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"13_CR101_13","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M. Samer","year":"2010","unstructured":"M. Samer and S. Szeider (2010). Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103\u2013114.","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR82_13","unstructured":"A. Scott (2010). The parameterized complexity of finding short winning strategies in combinatorial games. Ph.D. dissertation, University of Victoria."},{"key":"13_CR83_13","unstructured":"T. Shrot, Y. Aumann, and S. Kraus (2009). Easy and hard coalition resource game formation problems: a parameterized complexity analysis. AAMAS (1) 2009, 433\u2013440."},{"issue":"1","key":"13_CR84_13","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1093\/comjnl\/bxm038","volume":"51","author":"C Sloper","year":"2008","unstructured":"C. Sloper and J. A. Telle (2008). An overview of techniques for designing parameterized algorithms. The Computer Journal 51(1), 122\u2013136.","journal-title":"The Computer Journal"},{"key":"13_CR85_13","unstructured":"O. Suchy (2011). Parameterized complexity: nonstandard parameterizations of graph problems. Ph.D. dissertation, Charles University in Prague (Czech Republic)."},{"key":"13_CR86_13","doi-asserted-by":"crossref","unstructured":"S. Tazari, M. M\u00fcller-Hannemann (2009). Dealing with Large Hidden Constants: Engineering a Planar Steiner Tree PTAS. ALENEX 2009: 120\u2013131.","DOI":"10.1137\/1.9781611972894.12"},{"issue":"3","key":"13_CR102_13","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1093\/comjnl\/bxm034","volume":"51","author":"I. Rooij","year":"2008","unstructured":"I. van Rooij and T. Wareham (2008). Parameterized complexity in cognitive modeling: foundations, applications, and opportunities. The Computer Journal 51(3), 385\u2013404.","journal-title":"The Computer Journal"},{"key":"13_CR87_13","doi-asserted-by":"crossref","unstructured":"T. Walsh (2010). Parameterized complexity results in symmetry breaking. In: Proceedings of the Fifth International Symposium of Parameterized and Exact Computation 2010 (Chennai, India), Springer, LNCS (6478) 4\u201313.","DOI":"10.1007\/978-3-642-17493-3_3"}],"container-title":["Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4614-1168-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T14:59:35Z","timestamp":1706194775000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4614-1168-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9781461411673","9781461411680"],"references-count":82,"URL":"https:\/\/doi.org\/10.1007\/978-1-4614-1168-0_13","relation":{},"subject":[],"published":{"date-parts":[[2011]]},"assertion":[{"value":"22 October 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}