8 papers
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 $Ï(v)…
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…
-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 …
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…
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity)…
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 cen…