Shimon Kogan

collaborators

2 papers

cs.DS2026

$O ~ (1)$ -Depth Parallel Reachability Faster than Transitive Closure

Shimon Kogan, Merav Parter

A $d$ -shortcut of a directed graph $G = (V, E)$ is a subset of edges drawn from the transitive closure $T C (G)$ whose addition reduces the graph diameter to at most $d$ . In the special…

cs.DS2026

Multi-Source Reachability in Near-Optimal Time

Shimon Kogan, Merav Parter

The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For $n$ -vertex digraphs $G = (V, E)$ and a subset of sources $S \subse…

O~(1)-Depth Parallel Reachability Faster than Transitive Closure

Multi-Source Reachability in Near-Optimal Time

$O ~ (1)$ -Depth Parallel Reachability Faster than Transitive Closure