Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Stephan Kreutzer:

TR09-147 | 30th December 2009
Stephan Kreutzer

Algorithmic Meta-Theorems

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a
structural component, that is they are results of the form:
"every computational problem that can be formalised in a given logic L ... more >>>

TR09-131 | 2nd December 2009
Stephan Kreutzer, Anuj Dawar

Parameterized Complexity of First-Order Logic

Revisions: 2

We show that if $\mathcal C$ is a class of graphs which is
"nowhere dense" then first-order model-checking is
fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ... more >>>

ISSN 1433-8092 | Imprint