All reports by Author Stephan Kreutzer:

__
TR09-147
| 30th December 2009
__

Stephan Kreutzer#### Algorithmic Meta-Theorems

__
TR09-131
| 2nd December 2009
__

Stephan Kreutzer, Anuj Dawar#### Parameterized Complexity of First-Order Logic

Revisions: 2

Stephan Kreutzer

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 >>>

Stephan Kreutzer, Anuj Dawar

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 >>>