research
∙
08/10/2023
Comparing Width Parameters on Graph Classes
We study how the relationship between non-equivalent width parameters ch...
share
research
∙
03/13/2023
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
We investigate a relaxation of the notion of treewidth-fragility, namely...
research
∙
02/14/2023
Non-empty intersection of longest paths in H-free graphs
We make progress toward a characterization of the graphs H such that eve...
research
∙
05/30/2022
On algorithmic applications of sim-width and mim-width of (H_1, H_2)-free graphs
Mim-width and sim-width are among the most powerful graph width paramete...
research
∙
08/20/2020
Solving problems on generalized convex graphs via mim-width
A bipartite graph G=(A,B,E) is H-convex, for some family of graphs H, if...
research
∙
08/03/2020
List k-Colouring P_t-Free Graphs with No Induced 1-Subdivision of K_1,s: a Mim-width Perspective
A colouring of a graph G=(V,E) is a mapping c V→{1,2,…} such that c(u)≠ ...
research
∙
05/06/2020
Sublinear Longest Path Transversals and Gallai Families
We show that connected graphs admit sublinear longest path transversals....
research
∙
04/16/2020
Approximating Independent Set and Dominating Set on VPG graphs
We consider Independent Set and Dominating Set restricted to VPG graphs ...
research
∙
04/10/2020
Bounding the Mim-Width of Hereditary Graph Classes
A large number of NP-hard graph problems become polynomial-time solvable...
research
∙
03/05/2019
CPG graphs: Some structural and hardness results
In this paper we continue the systematic study of Contact graphs of Path...
research
∙
10/16/2018