I. Shabat

collaborators

4 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 $I^\pm$ if for every $u, v \in V$ there is a tree $T_{uv}\in\math…

cs.DS2025

A Unified Framework for Hopsets and Spanners

Ofer Neiman, Idan Shabat

Given an undirected graph $G = (V, E)$ , an {\em $(I^\pm, I^^{2})$ -spanner} $H = (V, E^{'})$ is a subgraph that approximately preserves distances; for every $u, v \in V$ , $d_H(u,v)\le Î±\cdot d_G(u,v)…

cs.DS2024

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.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…