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

Showing 2025Show all

2 papers · 1 filter

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…