HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Courcelle's Theorem: Looking for papers

Submitted by: @import:stackexchange-cs··
0
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?

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.