Publications (65)
Sparse Fault-Tolerant BFS Trees
Merav Parter, David Peleg
This paper addresses the problem of designing a sparse {\em fault-tolerant} BFS tree, or {\em FT-BFS tree} for short, namely, a sparse subgraph of the given network such 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…
Component Stability in Low-Space Massively Parallel Computation
Artur Czumaj, Peter Davies, Merav Parter
We study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) intr…
Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
Merav Parter
Fault tolerant distance preservers (spanners) are sparse subgraphs that preserve (approximate) distances between given pairs of vertices under edge or vertex failures. So-far, thes…
Planar Diameter via Metric Compression
Jason Li, Merav Parter
We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [S…
Near-Optimal Distributed Computation of Small Vertex Cuts
Merav Parter, Asaf Petruschka
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributed computing. Despite extensive research in this area, our understanding of the…