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 cs.DSShow all

29 papers · 1 filter

cs.DS2026

Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Ofer Neiman, Alon Spector

Let $G = (V, E)$ be a weighted undirected graph, with $n$ vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal…

cs.DS2024

Lightweight Near-Additive Spanners

Yuval Gitlitz, Ofer Neiman, Richard Spence

An $(α, β)$ -spanner of a weighted graph $G = (V, E)$ , is a subgraph $H$ such that for every $u, v \in V$ , $d_{G} (u, v) \leq d_{H} (u, v) \leq α \cdot d_{G} (u, v) + β$ . The main parameters of interest for…

cs.DS2024

Path-Reporting Distance Oracles with Linear Size

Ofer Neiman, Idan Shabat

Given an undirected weighted graph, an (approximate) distance oracle is a data structure that can (approximately) answer distance queries. A {\em Path-Reporting Distance Oracle}, o…

cs.DS2023

On the Size Overhead of Pairwise Spanners

Ofer Neiman, Idan Shabat

Given an undirected possibly weighted $n$ -vertex graph $G = (V, E)$ and a set $P \subseteq V^{2}$ of pairs, a subgraph $S = (V, E^{'})$ is called a $P$ -pairwise $α$ -spanner of…

cs.DS2023

Light, Reliable Spanners

Arnold Filtser, Yuval Gitlitz, Ofer Neiman

A \emph{ $ν$ -reliable spanner} of a metric space $(X, d)$ , is a (dominating) graph $H$ , such that for any possible failure set $B \subseteq X$ , there is a set $B^{+}$ just slightly larg…

cs.DS2021★ 1 cited

A Unified Framework for Hopsets and Spanners

Ofer Neiman, Idan Shabat

Given an undirected graph $G = (V, E)$ , an {\em $(α, β)$ -spanner} $H = (V, E^{'})$ is a subgraph that approximately preserves distances; for every $u, v \in V$ , $d_{H} (u, v) \leq α \cdot d_{G} (u, v) + β$ …