Courcelle's theorem
In mathematics, Courcelle's theorem refers to a result about graphs in monadic second-order logic. The result was first proved by Courcelle in 1990 and is considered the archetype of algorithmic meta-theorems.[1][2]
The meta-theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs where the treewidth is bounded.[1][2] The typical approach to proving Courcelle's theorem involves the construction of a finite bottom-up tree automaton that performs a tree decomposition of the graph to recognize it.[1]
References
- ^ a b c A Practical Approach to Courcelle's Theorem by Joachim Kneis and Alexander Langer, in "Electronic Notes in Theoretical Computer Science" Volume 251, 3 September 2009, Pages 65–81
- ^ a b Algorithms - ESA 2010: 18th Annual European Symposium edited by Mark de Berg and Ulrich Meyer 2010 ISBN 3642157742 pages 549-550