6 citations · 15 across the 5 of their papers we have counts for
Showing 2011 · cs.DSShow all
2 papers · 2 filters
cs.DS2011
Courcelle's Theorem - A Game-Theoretic Approach
Joachim Kneis, Alexander Langer, Peter Rossmanith
Courcelle's Theorem states that every problem definable in Monadic Second-Order logic can be solved in linear time on structures of bounded treewidth, for example, by constructing…
cs.DS2011★ 5 cited
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
Alexander Langer, Peter Rossmanith, Somnath Sikdar
We present an alternative proof of a theorem by Courcelle, Makowski and Rotics which states that problems expressible in MSO are solvable in linear time for graphs of bounded rankw…