| Article ID: | iaor201110075 |
| Volume: | 8 |
| Issue: | 4 |
| Start Page Number: | 568 |
| End Page Number: | 594 |
| Publication Date: | Nov 2011 |
| Journal: | Discrete Optimization |
| Authors: | Kneis Joachim, Rossmanith Peter, Langer Alexander |
| Keywords: | graphs |
MSO‐definable problems can be solved in linear time on graphs of bounded treewidth. Construction of tree automata often fails in practice due to state explosion. A new game‐theoretic approach is introduced to avoid the power set construction. Experiments indicate feasibility.