4 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…
Core congestion is inherent in hyperbolic networks
Victor Chepoi, Feodor F. Dragan, Yann Vaxès
We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network admits a core, thus answer…
An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances
Victor Chepoi, M. Seston
In this paper, we present a factor 16 approximation algorithm for the following NP-hard distance fitting problem: given a finite set X and a distance d on X, find a Robinsonian dis…