research
∙
02/09/2023
A new width parameter of graphs based on edge cuts: α-edge-crossing width
We introduce graph width parameters, called α-edge-crossing width and ed...
share
research
∙
07/14/2022
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Let ℱ be a family of graphs, and let p,r be nonnegative integers. The (p...
research
∙
02/24/2022
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
In a reduction sequence of a graph, vertices are successively identified...
research
∙
09/28/2021
A Unifying Framework for Characterizing and Computing Width Measures
Algorithms for computing or approximating optimal decompositions for dec...
research
∙
05/25/2021
On the Erdős-Pósa property for long holes in C_4-free graphs
We prove that there exists a function f(k)=𝒪(k^2 log k) such that for ev...
research
∙
05/04/2021
Classes of intersection digraphs with good algorithmic properties
An intersection digraph is a digraph where every vertex v is represented...
research
∙
09/28/2020
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
The canonical tree-decomposition theorem, given by Robertson and Seymour...
research
∙
08/02/2020
Tree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the...
research
∙
07/28/2020
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
The Cut Count technique and the rank-based approach have lead to sin...
research
∙
02/25/2020
Well-partitioned chordal graphs: obstruction set and disjoint paths
We introduce a new subclass of chordal graphs that generalizes split gra...
research
∙
11/11/2019
A polynomial kernel for 3-leaf power deletion
A graph G is an ℓ-leaf power of a tree T if V(G) is equal to the set of ...
research
∙
11/01/2019
Obstructions for bounded shrub-depth and rank-depth
Shrub-depth and rank-depth are dense analogues of the tree-depth of a gr...
research
∙
08/27/2019
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
We develop a framework for applying treewidth-based dynamic programming ...
research
∙
09/12/2018
Classes of graphs with no long cycle as a vertex-minor are polynomially χ-bounded
A class G of graphs is χ-bounded if there is a function f such that for...
research
∙
08/02/2018
Lean tree-cut decompositions: obstructions and algorithms
The notion of tree-cut width has been introduced by Wollan [The structur...
research
∙
03/20/2018
Packing and covering induced subdivisions
A graph class F has the induced Erdős-Pósa property if there exists a fu...
research
∙
03/09/2018
Generalized distance domination problems and their complexity on graphs of bounded mim-width
We generalise the family of (σ, ρ)-problems and locally checkable vertex...
research
∙
11/14/2017
A note on the complexity of Feedback Vertex Set parameterized by mim-width
We complement the recent algorithmic result that Feedback Vertex Set is ...
research
∙
11/02/2017