412 citations · 423 across the 12 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
cs.DS2022
SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time t…
cs.DS2022★ 1 cited
A logic-based algorithmic meta-theorem for mim-width
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ( for short) which extends existential with…