2011/02/04 by Alexander Langer, Peter Rossmanith, Langer, Alexander +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1102.0908
Submitted
arxiv created 2011/02/04 · openalex publication_date 2011/02/04 · arxiv updated 2011/02/07 · openalex created_date 2022/09/29 · openalex updated_date 2026/07/28
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 rankwidth. Our proof uses a game-theoretic approach and has the advantage of being self-contained, intuitive, and fairly easy to follow. In particular, our presentation does not assume any background in logic or automata theory. We believe that it is good to have alternative proofs of this important result. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle's Theorem for treewidth.