17 citations · 52 across the 16 of their papers we have counts for
18 papers
Additive Quasi-isometry via rooted graph partitions and layering partition
Dibyayan Chakraborty, Yann Vaxès
For a graph , denotes the class of all subdivisions of and denotes the treewidth of . In this paper, we prove the following. For $k\geq 1, R\g…
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…
Additive approximation algorithm for geodesic centers in -hyperbolic graphs
Dibyayan Chakraborty, Yann Vaxès
For an integer , the objective of \textsc{-Geodesic Center} is to find a set of isometric paths such that the maximum distance between any vertex …
Isometric path complexity of graphs
Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud +1
A set of isometric paths of a graph is ``-rooted'', where is a vertex of , if is one of the endpoints of all the isometric paths in . The isometric path co…
Sample compression schemes for balls in graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney +2
One of the open problems in machine learning is whether any set-family of VC-dimension admits a sample compression scheme of size . In this paper, we study this problem f…
ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and G-connected medians
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median function is a location/consensus function that maps any profile (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices fro…
Graphs with -connected medians
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median of a graph with weighted vertices is the set of all vertices minimizing the sum of weighted distances from to the vertices of . For any integer ,…
Optimizing the ecological connectivity of landscapes with generalized flow models and preprocessing
François Hamonic, Cécile Albert, Basile Couëtoux +1
In this paper we consider the problem of optimizing the ecological connectivity of a landscape under a budget constraint by improving habitat areas and ecological corridors between…
Medians in median graphs and their cube complexes in linear time
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median of a set of vertices of a graph is the set of all vertices of minimizing the sum of distances from to all vertices of . In this paper, we present…
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…
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
Victor Chepoi, Feodor Dragan, Ilan Newman +2
In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and sim…
Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
Nicolas Catusse, Victor Chepoi, Karim Nouioua +1
Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the distance between two points p,q in R^2 in the normed plane whose unit ball is B. For a set T of n points…
Cop and robber games when the robber can hide and ride
Jérémie Chalopin, Victor Chepoi, Nicolas Nisse +1
In the classical cop and robber game, two players, the cop C and the robber R, move alternatively along edges of a finite graph G. The cop captures the robber if both players are o…
Embedding into the rectilinear plane in optimal O*(n^2)
Nicolas Catusse, Victor Chepoi, Yann Vaxès
We present an optimal O*(n^2) time algorithm for deciding if a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l_1-metric. It improves…