I. Shabat

activity

20232025

collaborators

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