Showing 2022Show all
2 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.LO2022
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…