14 citations · 55 across the 23 of their papers we have counts for
3 papers · 1 filter
Fast approximation of centrality and distances in hyperbolic graphs
Victor Chepoi, Feodor F. Dragan, Michel Habib +2
We show that the eccentricities (and thus the centrality indices) of all vertices of a -hyperbolic graph can be computed in linear time with an additive one-sided erro…
Fast approximation and exact computation of negative curvature parameters of graphs
Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan +3
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov…
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)…