research
∙
02/14/2023
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Disjoint-paths logic, denoted 𝖥𝖮+𝖣𝖯, extends first-order logic (𝖥𝖮) with...
share
research
∙
07/06/2022
Distributed domination on sparse graph classes
We show that the dominating set problem admits a constant factor approxi...
research
∙
06/29/2022
Combinatorial and Algorithmic Aspects of Monadic Stability
Nowhere dense classes of graphs are classes of sparse graphs with rich s...
research
∙
11/29/2021
Local planar domination revisited
We show how to compute a 20-approximation of a minimum dominating set in...
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/13/2021
First-Order Logic with Connectivity Operators
First-order logic (FO) can express many algorithmic problems on graphs, ...
research
∙
05/08/2021
On set systems definable in sparse graph classes, discrepancy, and quantifier elimination
We study the (hereditary) discrepancy of definable set systems, which is...
research
∙
02/09/2021
Recursive Backdoors for SAT
A strong backdoor in a formula ϕ of propositional logic to a tractable c...
research
∙
12/04/2020
Constant round distributed domination on graph classes with bounded expansion
We show that the dominating set problem admits a constant factor approxi...
research
∙
10/06/2020
Dynamic Query Evaluation Over Structures with Low Degree
We consider the evaluation of first-order queries over classes of databa...
research
∙
07/05/2020