10 citations · 10 across the 3 of their papers we have counts for
3 papers
cs.DS2009★ 10 cited
Domination Problems in Nowhere-Dense Classes of Graphs
Anuj Dawar, Stephan Kreutzer
We investigate the parameterized complexity of generalisations and variations of the dominating set problem on classes of graphs that are nowhere dense. In particular, we show that…
cs.DM2009
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
Stephan Kreutzer, Siamak Tazari
Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that…
cs.LO2009
On the Parameterised Intractability of Monadic Second-Order Logic
Stephan Kreutzer
One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic is fixed-parameter tractable o…