6 citations · 13 across the 11 of their papers we have counts for
18 papers · 1 filter
A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
Guillaume Ducoffe
A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph is the largest distance between a central vertex and the…
On -unimodality of radius functions in graphs: structure and algorithms
Jérémie Chalopin, Victor Chepoi, Feodor Dragan +2
For every weight assignment to the vertices in a graph , the radius function maps every vertex of to its largest weighted distance to the other vertices. The cente…
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…
Quasilinear-time eccentricities computation, and more, on median graphs
Pierre Bergé, Guillaume Ducoffe, Michel Habib
Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph cla…
Balancing graph Voronoi diagrams with one more vertex
Guillaume Ducoffe
Let be a graph with unit-length edges and nonnegative costs assigned to its vertices. Being given a list of pairwise different vertices , the {\em…
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…