5 papers
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…
Convergecast and Broadcast by Power-Aware Mobile Agents
Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz +3
A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery -- a power source allowing it to move along network edges. An agent uses its battery p…
Bidirected minimum Manhattan network problem
Nicolas Catusse, Victor Chepoi, Karim Nouioua +1
In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that t…