O. Neiman

activity

20062026

most citedNearly Tight Low Stretch Spanning Trees

25 citations · 49 across the 22 of their papers we have counts for

collaborators

Showing 2019Show all

4 papers · 1 filter

cs.DS2019

Lossless Prioritized Embeddings

Michael Elkin, Ofer Neiman

Given metric spaces $(X, d)$ and $(Y, ρ)$ and an ordering $x_{1}, x_{2}, \dots, x_{n}$ of $(X, d)$ , an embedding $f : X \to Y$ is said to have a prioritized distortion $α (\cdot)$ , if f…

cs.DS2019

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Michael Elkin, Yuval Gitlitz, Ofer Neiman

Let $G = (V, E, w)$ be a weighted undirected graph with $n$ vertices and $m$ edges, and fix a set of $s$ sources $S \subseteq V$ . We study the problem of computing {\em almost shortest…

cs.DS2019★ 1 cited

Covering Metric Spaces by Few Trees

Yair Bartal, Nova Fandina, Ofer Neiman

A {\em tree cover} of a metric space $(X, d)$ is a collection of trees, so that every pair $x, y \in X$ has a low distortion path in one of the trees. If it has the stronger property…

cs.DS2019

Distributed Construction of Light Networks

Michael Elkin, Arnold Filtser, Ofer Neiman

A $t$ -{\em spanner} $H$ of a weighted graph $G = (V, E, w)$ is a subgraph that approximates all pairwise distances up to a factor of $t$ . The {\em lightness} of $H$ is defined as the r…