6 citations · 13 across the 7 of their papers we have counts for
16 papers
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
Feodor F. Dragan, Guillaume Ducoffe, Heather M. Guarnera
A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. The class of Helly graphs is the discrete analogue of the class of hyperconvex m…
Beyond Helly graphs: the diameter problem on absolute retracts
Guillaume Ducoffe
Characterizing the graph classes such that, on -vertex -edge graphs in the class, we can compute the diameter faster than in time is an important research prob…
Optimal diameter computation within bounded clique-width graphs
Guillaume Ducoffe
Coudert et al. (SODA'18) proved that under the Strong Exponential-Time Hypothesis, for any , there is no -time algorithm for computing the diameter…
Distance problems within Helly graphs and -Helly graphs
Guillaume Ducoffe
The ball hypergraph of a graph is the family of balls of all possible centers and radii in . It has Helly number at most if every subfamily of -wise intersecting ball…
Around the diameter of AT-free graphs
Guillaume Ducoffe
A graph algorithm is truly subquadratic if it runs in time on connected -edge graphs, for some positive . Roditty and Vassilevska Williams (STOC'13) prove…
Isometric embeddings in trees and their use in the diameter problem
Guillaume Ducoffe
We prove that given a discrete space with points which is either embedded in a system of trees, or the Cartesian product of trees, we can compute all eccentricities in…