71 citations · 112 across the 28 of their papers we have counts for
5 papers · 1 filter
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…
Eccentricity queries and beyond using Hub Labels
Guillaume Ducoffe
Hub labeling schemes are popular methods for computing distances on road networks and other large complex networks, often answering to a query within a few microseconds for graphs…