71 citations · 112 across the 28 of their papers we have counts for
35 papers
Towards a more structured search for Erdős-Gyárfás counter-examples
Guillaume Ducoffe, Bogdan Dumitru
The Erdős-Gyárfás conjecture posits that every graph with minimum degree at least three contains a cycle of length some power of two. We prove a few simple structural properties fo…
Beyond Trees: The Weighted Center Problem on Gromov Hyperbolic Graphs
Guillaume Ducoffe
The Weighted Center} problem takes as its input a graph together with a profile such that every vertex is mapped to some nonnegative multiplicative weight .…
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…
Bow Metrics and Hyperbolicity
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
A ()-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an -metric (which is equivalent to a ()-bow metric). A graph is…
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…
Practical Computation of Graph VC-Dimension
David Coudert, Mónika Csikós, Guillaume Ducoffe +1
For any set system , a subset is called \emph{shattered} if every results from the intersection of with some set in…
-Metric Graphs: Hyperbolicity
Feodor F. Dragan, Guillaume Ducoffe
A graph is called -metric () if it satisfies the following -metric property for every vertices and : if a shortest path between and a…
-Metric Graphs: Radius, Diameter and all Eccentricities
Feodor F. Dragan, Guillaume Ducoffe
We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph…
Pattern detection in ordered graphs
Guillaume Ducoffe, Laurent Feuilloley, Michel Habib +1
A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead…
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…
Obstructions to faster diameter computation: Asteroidal sets
Guillaume Ducoffe
An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let be the class of all connected graphs wh…
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…
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…
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…
A story of diameter, radius and Helly property
Feodor F. Dragan, Guillaume Ducoffe
A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. Motivated by previous work on dually chordal graphs and graphs of bounded distan…
Fast Diameter Computation within Split Graphs
Guillaume Ducoffe, Michel Habib, Laurent Viennot
When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deci…
Diameter computation on -minor free graphs and graphs of bounded (distance) VC-dimension
Guillaume Ducoffe, Michel Habib, Laurent Viennot
We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-…