Michael Elkin

collaborators

Showing cs.DSShow all

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

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…