Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Courcelle:
TR10-062 | 7th April 2010
Michael Elberfeld, Andreas Jakoby, Till Tantau

Logspace Versions of the Theorems of Bodlaender and Courcelle

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for
every $k$ there is ... more >>>

TR14-134 | 10th October 2014
Martin Lück, Arne Meier, Irina Schindler

Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies

Revisions: 3

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>>

ISSN 1433-8092 | Imprint