Monadic Datalog over Finite Structures with Bounded Treewidth (2008)
Gottlob, Georg, Pichler, Reinhard, Wei, Fang
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know: Any property of...
A Backtracking-Based Algorithm for Computing Hypertree-Decompositions (2007)
Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the cyclicity and therefore tractability of the...