Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALGORITHMIC META-THEOREMS:
Reports tagged with algorithmic meta-theorems:
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