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

2 papers · 2 filters

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…