Michael Elkin

activity

20242026

collaborators

3 papers

cs.DS2026

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication

Michael Elkin, Chhaya Trehan

Given an $n$ -vertex $m$ -edge digraph $G = (V, E)$ and a subset $S \subseteq V$ of $∣ S ∣ = n^{I ¨} $ (for some $0 \leq I ¨ \leq 1$ ) designated sources, the $S \times V$ reachability problem i…

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