Martin Grohe
- H.L. Bodlaender, R.G. Downey, M.R. Fellows, M.T. Hallett, and H.T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11:49--57, 1995.]]Google Scholar
- 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--90, 1977.]] Google ScholarDigital Library
- B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 2, pages 194--242. Elsevier Science Publishers, 1990.]] Google ScholarDigital Library
- R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24:873--921, 1995.]] Google ScholarDigital Library
- R.G. Downey and M.R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W {1}. Theoretical Computer Science, 141:109--131, 1995.]] Google ScholarDigital Library
- R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.]]Google ScholarDigital Library
- R.G. Downey, M.R. Fellows, and U. Taylor. The parameterized complexity of relational database queries and an improved characterization of W {I}. In D.S. Bridges, C. Calude, P. Gibbons, S. Reeves, and I.H. Witten, editors, Combinatorics, Complexity, and Logic--Proceedings of DMTCS '96, pages 194--213. Springer-Verlag, 1996.]]Google Scholar
- E.A. Emerson and C.-L. Lei. Modalities for model checking: Branching time logic strikes back. Science of Computer Programming, 8(3):275--306, 1987.]] Google ScholarDigital Library
- J. Flum, M. Frick, and M. Grohe. Query evaluation via tree-decompositions. Currently available at http://www.dcs.ed.ac.uk/~grohe. A preliminary version of the paper appeared in Proceedings of the 8th International Conference on Database Theory, LNCS 1973, Springer-Verlag, 2001.]] Google ScholarDigital Library
- J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing, 31(1):113--145, 2001.]] Google ScholarDigital Library
- M. Frick. Generalized model-checking over locally tree-decomposable classes. In H. Alt and A. Ferreira, editors, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, volume 2285 of Lecture Notes in Computer Science, pages 632--644. Springer-Verlag, 2002.]] Google ScholarDigital Library
- M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM, 48:1184 -- 1206, 2001.]] Google ScholarDigital Library
- M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. In Proceedings of the 17th IEEE Symposium on Logic in Computer Science, pages 215--224, 2002.]] Google ScholarDigital Library
- G. Gottlob and C. Koch. Monadic queries over tree-structured data. In Proceedings of the 17th IEEE Symposium on Logic in Computer Science, pages 189--202, 2002.]] Google ScholarDigital Library
- G. Gottlob, N. Leone, and M. Sideri. Fixed-parameter complexity in AI and nonmonotonic reasoning. In M. Gelfond, N. Leone, and G. Pfeifer, editors, Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR'99, volume 1730 of Lecture Notes in Computer Science, pages 1--18. Springer-Verlag, 1999.]] Google Scholar
- M. Grohe. The parameterized complexity of database queries. In Proceedings of the 20th ACM Symposium on Principles of Database Systems, pages 82--92, 2001.]] Google ScholarDigital Library
- O. Lichtenstein and A. Pnueli. Finite state concurrent programs satisfy their linear specification. In Proceedings of the Twelfth ACM Symposium on the Principles of Programming Languages, pages 97--107, 1985.]] Google ScholarDigital Library
- F. Neven and T. Schwentick. Expressive and efficient pattern languages for tree-structured data. In Proceedings of the 19th ACM Symposium on Principles of Database Systems, pages 145--156, 2000.]] Google ScholarDigital Library
- C.H. Papadimitriou and M. Yannakakis. On the complexity of database queries. Journal of Computer and System Sciences, 58:407--427, 1999.]] Google ScholarDigital Library
- D. Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6:505--526, 1996.]]Google ScholarCross Ref
- U. Stege. Resolving Conflicts in Problems from Computational Biology. PhD thesis, ETH Zuerich, 2000. PhD Thesis No. 13364.]]Google Scholar
- L.J. Stockmeyer. The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974.]]Google Scholar
- J.W. Thatcher and J.B. Wright. Generalised finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2:57--81, 1968.]]Google ScholarCross Ref
- M.Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137--146, 1982.]] Google ScholarDigital Library
- M. Yannakakis. Perspectives on database theory. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 224--246, 1995.]] Google ScholarDigital Library
Index Terms
- Parameterized complexity for the database theorist
Index terms have been assigned to the content through auto-classification.
Recommendations
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
On parameterized exponential time complexity
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...
Parameterized Complexity of Graph Burning
AbstractGraph Burning asks, given a graph and an integer k, whether there exists such that every vertex in G has distance at most i from some . This problem is known to be NP-complete even on connected caterpillars of maximum ...
Comments