{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:39:49Z","timestamp":1725896389133},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642102165"},{"type":"electronic","value":"9783642102172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10217-2_2","type":"book-chapter","created":{"date-parts":[[2009,11,9]],"date-time":"2009-11-09T15:52:03Z","timestamp":1257781923000},"page":"2-10","source":"Crossref","is-referenced-by-count":22,"title":["Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology"],"prefix":"10.1007","author":[{"given":"Michael","family":"Fellows","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Hallett, M.: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pp. 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Koster, A.M.: Combinatorial optimisation on graphs of bounded treewidth. The Computer Journal\u00a051, 255\u2013269 (2007)","journal-title":"The Computer Journal"},{"key":"2_CR4","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 width. SIAM J. Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Computing"},{"key":"2_CR5","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., Kanj, I., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation\u00a0201, 216\u2013231 (2005)","journal-title":"Information and Computation"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Fellows, M., Downey, R., Langston, M. (Guest eds.): The Computer Journal: Two special issues of surveys of various aspects of parameterized complexity and algorithmics. The Computer Journal\u00a051(1&3) (2008)","DOI":"10.1093\/comjnl\/bxm111"},{"key":"2_CR7","doi-asserted-by":"publisher","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. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1002\/jgt.3190160509","volume":"16","author":"G. Ding","year":"1992","unstructured":"Ding, G.: Subgraphs and well-quasi-ordering. J. Graph Theory\u00a016, 489\u2013502 (1992)","journal-title":"J. Graph Theory"},{"key":"2_CR9","first-page":"205","volume":"78","author":"R. Downey","year":"2003","unstructured":"Downey, R., Estivill-Castro, V., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electron. Notes Theor. Comp. Sci.\u00a078, 205\u2013218 (2003)","journal-title":"Electron. Notes Theor. Comp. Sci."},{"key":"2_CR10","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, Heidelberg (1999)"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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., Hallett, M., Kapron, B., 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":"2_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"Parameterized approximation for dominating set problems","year":"2008","unstructured":"Parameterized approximation for dominating set problems. Information Processing Letters\u00a0109, 68\u201370 (2008)","journal-title":"Information Processing Letters"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Graham, R., Kratochvil, J., Nesetril, J., Roberts, F. (eds.) Contemporary Trends in Discrete Mathematics, Proceedings of the DIMACS-DIMATIA Workshop on the Future of Discrete Mathematics, Prague, 1997. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-540-73556-4_38","volume-title":"Combinatorial Optimization and Applications","author":"M. Fellows","year":"2007","unstructured":"Fellows, M., Fomin, F., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA 2007. LNCS, vol.\u00a04616, pp. 366\u2013377. Springer, Heidelberg (2007)"},{"key":"2_CR15","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of IWPEC 2009","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F.: Well-quasi-ordering bounded treewidth graphs. In: Proceedings of IWPEC 2009. LNCS, vol.\u00a05917. Springer, Heidelberg (to appear)"},{"key":"2_CR17","unstructured":"Fellows, M., Hermelin, D., Rosamond, F.: Parameter ecology, well-quasi-ordering and universal antichains (manuscript, 2009)"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"M. Fellows","year":"2008","unstructured":"Fellows, M., Lokshtanov, D., Misra, N., Rosamond, F., Saurabh, S.: Graph Layout Problems Parameterized by Vertex Cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory of Computing Systems (2009)","DOI":"10.1007\/s00224-009-9167-9"},{"key":"2_CR20","first-page":"119","volume-title":"Proc. Symp. on Principles of Programming Languages (POPL)","author":"F. Henglein","year":"1991","unstructured":"Henglein, F., Mairson, H.G.: The complexity of type inference for higher-order typed lambda calculi. In: Proc. Symp. on Principles of Programming Languages (POPL), pp. 119\u2013130. ACM Press, New York (1991)"},{"key":"2_CR21","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.: Which problems have strongly exponential complexity? J. Computer and Systems Sciences\u00a063, 512\u2013530 (2001)","journal-title":"J. Computer and Systems Sciences"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Lichtenstein, O., Pneuli, A.: Checking That Finite-State Concurrents Programs Satisfy Their Linear Specification. In: Proceedings of the 12th ACM Symposium on Principles of Programming Languages, pp. 97\u2013107 (1985)","DOI":"10.1145\/318593.318622"},{"key":"2_CR23","doi-asserted-by":"publisher","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":"2_CR24","first-page":"153","volume-title":"Surveys in Combinatorics","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.: Graph minors: a survey. In: Anderson, J. (ed.) Surveys in Combinatorics, pp. 153\u2013171. Cambridge University Press, Cambridge (1985)"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.: Graph minors XX. Wagner\u2019s conjecture. J. Comb. Th. Series B\u00a092, 325\u2013357 (2004)","journal-title":"J. Comb. Th. Series B"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-540-85238-4_49","volume-title":"Mathematical Foundations of Computer Science 2008","author":"S. Szeider","year":"2008","unstructured":"Szeider, S.: Monadic second order logic on graphs with local cardinality constraints. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 601\u2013612. Springer, Heidelberg (2008)"},{"key":"2_CR27","unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. In: Proc. ICDM 2008 (to appear)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10217-2_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:52:17Z","timestamp":1606186337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10217-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642102165","9783642102172"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10217-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}