Michael Elkin

activity

20232025

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

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

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 $α$ if for every $u, v \in V$ there is a tree $T_{uv}\in\mathc…

cs.DS2025

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^{σ}$ (for some $0 \leq σ \leq 1$ ) designated sources, the $S \times V$ reachability problem is…

cs.DS2024

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Michael Elkin, Chhaya Trehan

Given an $n$ -vertex $m$ -edge digraph $G = (V, E)$ and a set $S \subseteq V$ , $∣ S ∣ = n^{σ}$ (for some $0 < σ \leq 1$ ) of designated sources, the $S \times V$ -direachability problem is to…

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