All reports by Author Michael Elberfeld:

__
TR12-150
| 1st November 2012
__

Michael Elberfeld, Christoph Stockhusen, Till Tantau#### On the Space Complexity of Parameterized Problems

Revisions: 1

__
TR11-128
| 21st September 2011
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

__
TR10-062
| 7th April 2010
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Logspace Versions of the Theorems of Bodlaender and Courcelle

Michael Elberfeld, Christoph Stockhusen, Till Tantau

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

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

Michael Elberfeld, Andreas Jakoby, Till Tantau

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