Inhalt des Dokuments
Implementing Courcelle's Theorem
Peter Rossmanith (Prof. RWTH Aachen)
A direct implementation of Courcelle's Theorem poses many practical problems. Some of them can be avoided when using a game-theoretic instead of an automata based approach, which Courcelle's original proof uses. A demonstration of the resulting implementation shows that several non-trivial problems can be solved by this approach if the tree-width is not too large.
Back to the research colloquium site.