19 citations · 110 across the 50 of their papers we have counts for
5 papers · 2 filters
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…
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
Artur Czumaj, Peter Davies, Merav Parter
The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (t…
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
Merav Parter
We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, so…
New Spanners and Hopsets
Uri Ben-Levy, Merav Parter
An -spanner of an unweighted -vertex graph is a subgraph satisfying that is at most for every . We present new sp…
Local Computation Algorithms for Spanners
Merav Parter, Ronitt Rubinfeld, Ali Vakilian +1
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in t…