8 citations · 66 across the 52 of their papers we have counts for
9 papers · 1 filter
Modulo-Counting First-Order Logic on Bounded Expansion Classes
J. Nesetril, P. Ossona de Mendez, S. Siebertz
We prove that, on bounded expansion classes, every first-order formula with modulo counting is equivalent, in a linear-time computable monadic expansion, to an existential first-or…
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the…
On first-order transductions of classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether o…
Distributed domination on sparse graph classes
Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez +2
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…
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…