research
∙
07/04/2023
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Twin-width is a structural width parameter introduced by Bonnet, Kim, Th...
share
research
∙
07/01/2023
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Let d be a positive integer. For a finite set X ⊆ℝ^d, we define its inte...
research
∙
04/04/2023
Dynamic treewidth
We present a data structure that for a dynamic graph G that is updated b...
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
∙
01/06/2023
Simpler and faster algorithms for detours in planar digraphs
In the directed detour problem one is given a digraph G and a pair of ve...
research
∙
03/09/2022
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
We revisit recent developments for the Maximum Weight Independent Set pr...
research
∙
02/15/2022
Graphs of bounded twin-width are quasi-polynomially χ-bounded
We prove that for every t∈ℕ there is a constant γ_t such that every grap...
research
∙
10/15/2021
Compact representation for matrices of bounded twin-width
For every fixed d ∈ℕ, we design a data structure that represents a binar...
research
∙
07/13/2021
Maintaining 𝖢𝖬𝖲𝖮_2 properties on dynamic structures with bounded feedback vertex number
Let φ be a sentence of 𝖢𝖬𝖲𝖮_2 (monadic second-order logic with quantific...
research
∙
05/04/2021
Determining 4-edge-connected components in linear time
In this work, we present the first linear time deterministic algorithm c...
research
∙
03/10/2021