Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Martin Grohe:

TR07-106 | 10th September 2007
Yijia Chen, Martin Grohe, Magdalena GrĂ¼ber

On Parameterized Approximability

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.
The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

more >>>

TR07-091 | 10th September 2007
Martin Grohe

Logic, Graphs, and Algorithms

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>>

TR06-011 | 2nd January 2006
Yijia Chen, Martin Grohe

An Isomorphism between Subexponential and Parameterized Complexity Theory

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

more >>>

ISSN 1433-8092 | Imprint