Chhaya Trehan

collaborators

2 papers

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.DC2014

Fast and Compact Distributed Verification and Self-Stabilization of a DFS Tree

Shay Kutten, Chhaya Trehan

We present algorithms for distributed verification and silent-stabilization of a DFS(Depth First Search) spanning tree of a connected network. Computing and maintaining such a DFS…