Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TREE DEPTH:
Reports tagged with tree depth:
TR11-128 | 21st September 2011
Michael Elberfeld, Andreas Jakoby, Till Tantau

Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>




ISSN 1433-8092 | Imprint