412 citations · 423 across the 12 of their papers we have counts for
6 papers · 1 filter
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz +1
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attent…
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…
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…
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…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…