4 papers
On density of subgraphs of halved cubes
Victor Chepoi, Arnaud Labourel, Sébastien Ratel
Let be a family of subsets of a set of cardinality and be the Vapnik-Chervonenkis dimension of . Haussler, Littlestone,…
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…
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…
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…