{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T03:47:59Z","timestamp":1777348079682,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540665366","type":"print"},{"value":"9783540481683","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48168-0_3","type":"book-chapter","created":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T11:30:26Z","timestamp":1196508626000},"page":"14-31","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Descriptive and Parameterized Complexity"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8:277\u2013284,1987.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308\u2013340, 1991.","journal-title":"Journal of Algorithms"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"N. Alon, R. Yuster, and U. Zwick. Color-coding. Journal of the ACM,42:844\u2013856, 1995.","journal-title":"Journal of the ACM"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR5","series-title":"Lect Notes Comput Sci","first-page":"29","volume-title":"Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS\u201997","author":"H.L. Bodlaender","year":"1997","unstructured":"H.L. Bodlaender. Treewidth: Algorithmic techniques and results. In I. Privara and P. Ruzicka, editors, Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS\u201997, volume 1295 of Lecture Notes in Computer Science, pages 29\u201336. Springer-Verlag, 1997."},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th ACM Symposium on Theory of Computing, pages 77\u201390, 1977.","DOI":"10.1145\/800105.803397"},{"key":"3_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/10692760_1","volume-title":"Graph Theoretic Concepts in Computer Science, WG\u201998","author":"B. Courcelle","year":"1998","unstructured":"B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique width. In Graph Theoretic Concepts in Computer Science, WG\u201998, volume 1517 of Lecture Notes in Computer Science, pages 1\u201316. Springer-Verlag, 1998."},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194\u2013242. Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141:109\u2013131, 1995.","journal-title":"Theoretical Computer Science"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows. Parametrized Complexity. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows, and K. Regan. Descriptive complexity and the W-hierarchy. In P. Beame and S. Buss, editors, Proof Complexity and Feasible Arithmetic, volume 39 of AMS-DIMACS Volume Series, pages 119\u2013134. AMS, 1998.","DOI":"10.1090\/dimacs\/039\/07"},{"key":"3_CR12","unstructured":"R.G. Downey, M.R. Fellows, and U. Taylor. The parametrized complexity of relational database queries and an improved characterization of W[1]. In Bridges, Calude, Gibbons, Reeves, and Witten, editors, Combinatorics, Complexity, and Logic Proceedings-of DMTCS\u2019 96, pages 194\u2013213. Springer-Verlag, 1996."},{"key":"3_CR13","unstructured":"R. Diestel. Graph Theory. Springer-Verlag, 1997."},{"key":"3_CR14","unstructured":"J. Flum and M. Grohe. Fixed-parameter tractability and logic. In preparation."},{"key":"3_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-48523-6_30","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming","author":"M. Frick","year":"1999","unstructured":"M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable graphs. In J. Wiedermann, P. van Emde Boas, M. Nielsen. editors, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 331\u2013340. Springer-Verlag, 1999."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"T. Feder and M.Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the 25th ACM Symposium on Theory of Computing, pages 612\u2013622, 1993.","DOI":"10.1145\/167088.167245"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium\u2019 81. North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237\u2013267, 1976.","journal-title":"Theoretical Computer Science"},{"key":"3_CR19","unstructured":"M. Grohe and K. Luosto. Private communication."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R. Halin","year":"1976","unstructured":"R. Halin. S-Functions for graphs. Journal of Geometry, 8:171\u2013186, 1976.","journal-title":"Journal of Geometry"},{"key":"3_CR21","first-page":"132","volume":"68","author":"W. Hanf","year":"1965","unstructured":"W. Hanf. Model-theoretic methods in the study of elementary logic. In J. Addison, L. Henkin, and A. Tarski, editors, The Theory of Models, pages 132\u2013145. North Holland, 1965. au][Imm86] N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp. Reducibilities among combinatorial problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, New York, 1972."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-query containment and constraint satisfaction. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, pages 205\u2013213, 1998.","DOI":"10.1145\/275487.275511"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"B. Mohar. Embedding graphs in an arbitrary surface in linear time. In Proceedings of the 28th ACM Symposium on Theory of Computing, pages 392\u2013397, 1996.","DOI":"10.1145\/237814.237986"},{"key":"3_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/3-540-53832-1_28","volume-title":"Graph-Theoretic Concepts in Computer Science, WG\u2019 90","author":"J. Plehn","year":"1990","unstructured":"J. Plehn and B. Voigt. Finiding minimally weighted subgraphs. In R. M\u00f6hring, editor, Graph-Theoretic Concepts in Computer Science, WG\u2019 90, volume 484 of Lecture Notes in Computer Science, pages 18\u201329. Springer-Verlag, 1990."},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis. On the complexity of database queries. In Proceedings of the 16th ACM Symposium on Principles of Database Systems, pages 12\u201319, 1997.","DOI":"10.1145\/263661.263664"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors II. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309\u2013322, 1986.","journal-title":"Journal of Algorithms"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41:92\u2013114, 1986.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"N. Robertson and P.D. Seymour. Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63:65\u2013110, 1995.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3_CR30","unstructured":"N. Robertson and P.D. Seymour. Graph minors XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B. To appear."},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D. Seese","year":"1996","unstructured":"D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6:505\u2013526, 1996.","journal-title":"Mathematical Structures in Computer Science"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"L.J. Stockmeyer and A.R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on Theory of Computing, pages 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J.P. Schmidt","year":"1990","unstructured":"J.P. Schmidt and A. Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing, 19:775\u2013786, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. On the complexity of bounded-variable queries. In Proceedings of the 14th ACM Symposium on Principles of Database Systems, pages 266\u2013276, 1995.","DOI":"10.1145\/212433.212474"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"M. Yannakakis. Perspectives on database theory. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 224\u2013246, 1995.","DOI":"10.1109\/SFCS.1995.492479"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48168-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T03:45:48Z","timestamp":1737603948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48168-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540665366","9783540481683"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-48168-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"13 May 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}