I. Shabat

activity

20212025

most citedPath-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)

1 citations · 2 across the 4 of their papers we have counts for

collaborators

5 papers

cs.DS2025

Spanning Tree Covers for Path-Separable Graphs: Trading Stretch for Size

Michael Elkin, Idan Shabat

Given a graph $G = (V, E)$ , a collection $T$ of spanning trees of $G$ is called a spanning tree cover of stretch $α$ if for every $u, v \in V$ there is a tree $T_{uv}\in\mathc…

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★ 1 cited

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)

Michael Elkin, Idan Shabat

Given an $n$ -vertex undirected graph $G = (V, E, w)$ , and a parameter $k \geq 1$ , a path-reporting distance oracle (or PRDO) is a data structure of size $S (n, k)$ , that given a query $(u,…

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) + β$ …