71 citations · 112 across the 28 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
Pierre Bergé, Guillaume Ducoffe, Michel Habib
On sparse graphs, Roditty and Williams [2013] proved that no -time algorithm achieves an approximation factor smaller than for the diameter prob…
cs.DS2021
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…
math.CO2021
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…