54 citations · 245 across the 46 of their papers we have counts for
5 papers · 1 filter
Shortest path problem in rectangular complexes of global nonpositive curvature
Victor Chepoi, Daniela Maftuleac
CAT(0) metric spaces constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a CAT(0) metric space are con…
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…
Ramified rectilinear polygons: coordinatization by dendrons
Hans-Jürgen Bandelt, Victor Chepoi, David Eppstein
Simple rectilinear polygons (i.e. rectilinear polygons without holes or cutpoints) can be regarded as finite rectangular cell complexes coordinatized by two finite dendrons. The in…
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…