research
∙
03/02/2023
Canonical decompositions in monadically stable and bounded shrubdepth graph classes
We use model-theoretic tools originating from stability theory to derive...
share
research
∙
02/01/2023
Flip-width: Cops and Robber on dense graphs
We define new graph parameters, called flip-width, that generalize treew...
research
∙
01/31/2023
Flipper games for monadically stable graph classes
A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...
research
∙
06/28/2022
Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
An indiscernible sequence (a̅_i)_1≤ i≤ n in a structure is an ordered se...
research
∙
06/16/2022
Twin-width and types
We study problems connected to first-order logic in graphs of bounded tw...
research
∙
02/25/2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
We present a fixed-parameter tractable algorithm for first-order model c...
research
∙
01/26/2022
Treelike decompositions for transductions of sparse graphs
We give new decomposition theorems for classes of graphs that can be tra...
research
∙
11/05/2021
Algorithms and data structures for first-order logic with connectivity under vertex failures
We introduce a new data structure for answering connectivity queries in ...
research
∙
07/08/2021
Stable graphs of bounded twin-width
We prove that every class of graphs 𝒞 that is monadically stable and has...
research
∙
02/13/2021
Ordered graphs of bounded twin-width
We consider hereditary classes of graphs equipped with a total order. We...
research
∙
01/11/2021
Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
We introduce a model of register automata over infinite trees with extre...
research
∙
12/27/2019
Aggregate Queries on Sparse Databases
We propose an algebraic framework for studying efficient algorithms for ...
research
∙
11/16/2018
Progressive Algorithms for Domination and Independence
We consider a generic algorithmic paradigm that we call progressive expl...
research
∙
10/04/2018
First-order interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
research
∙
05/09/2018
Parameterized circuit complexity of model checking first-order logic on sparse structures
We prove that for every class C of graphs with effectively bounded expan...
research
∙
02/23/2018