patternMinor
Courcelle's Theorem: Looking for papers
Viewed 0 times
courcellelookingpapersfortheorem
Problem
I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.
I am only a beginner in this field.
Any suggestions?
I am only a beginner in this field.
Any suggestions?
Solution
There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.
Context
StackExchange Computer Science Q#16324, answer score: 4
Revisions (0)
No revisions yet.