research
∙
05/23/2023
Parameterized Complexity Classification for Interval Constraints
Constraint satisfaction problems form a nicely behaved class of problems...
share
research
∙
08/04/2022
Almost Consistent Systems of Linear Equations
Checking whether a system of linear equations is consistent is a basic c...
research
∙
01/27/2022
An Algorithmic Framework for Locally Constrained Homomorphisms
A homomorphism f from a guest graph G to a host graph H is locally bijec...
research
∙
07/03/2021
Solving Infinite-Domain CSPs Using the Patchwork Property
The constraint satisfaction problem (CSP) has important applications in ...
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
∙
06/05/2020
Clique-Width: Harnessing the Power of Atoms
Many NP-complete graph problems are polynomially solvable on graph class...
research
∙
10/11/2019
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Let vc(G), fvs(G) and oct(G), respectively, denote the size of a minimum...
research
∙
08/01/2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
A graph is H-free if it contains no induced subgraph isomorphic to H. We...
research
∙
01/02/2019
Clique-Width for Hereditary Graph Classes
Clique-width is a well-studied graph parameter owing to its use in under...
research
∙
11/29/2018
Graph Isomorphism for (H_1,H_2)-free Graphs: An Almost Complete Dichotomy
We consider the Graph Isomorphism problem for classes of graphs characte...
research
∙
08/10/2018
Finding a Small Number of Colourful Components
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not nec...
research
∙
11/23/2017
Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
Daligault, Rao and Thomassé asked whether every hereditary graph class t...
research
∙
07/22/2016
Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide
A graph is (H_1,H_2)-free for a pair of graphs H_1,H_2 if it contains no...
research
∙
06/22/2015