17 citations · 52 across the 16 of their papers we have counts for
3 papers · 1 filter
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…