19 citations · 110 across the 50 of their papers we have counts for
47 papers · 1 filter
-Depth Parallel Reachability Faster than Transitive Closure
Shimon Kogan, Merav Parter
A -shortcut of a directed graph is a subset of edges drawn from the transitive closure whose addition reduces the graph diameter to at most . In the special…
Space-Optimal Sensitivity Oracles for Single-Source Mincuts
Koustav Bhanja, Merav Parter, Asaf Petruschka
We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to source change…
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 -vertex digraphs and a subset of sources $S \subse…
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
Julia Chuzhoy, Merav Parter
A -spanner of an undirected -vertex graph is a sparse subgraph of that preserves all pairwise distances between its vertices to within multiplicative factor ,…
All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
Orr Fischer, Merav Parter
Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts th…
New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
Yuval Gil, Merav Parter
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a \emph{distributed interactive proof} (DIP) was introduced by Kol, Oshm…