research
∙
07/15/2022
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
For any ε > 0, we give a polynomial-time n^ε-approximation algorithm for...
share
research
∙
04/12/2022
1-Extendability of independent sets
In the 70s, Berge introduced 1-extendable graphs (also called B-graphs),...
research
∙
12/16/2021
Deciding twin-width at most 4 is NP-complete
We show that determining if an n-vertex graph has twin-width at most 4 i...
research
∙
10/06/2021
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
On sparse graphs, Roditty and Williams [2013] proved that no O(n^2-ε)-ti...
research
∙
05/25/2021
Diameter, radius and all eccentricities in linear time for constant-dimension median graphs
Median graphs form the class of graphs which is the most studied in metr...
research
∙
07/04/2019