19 citations · 110 across the 50 of their papers we have counts for
4 papers · 2 filters
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Shimon Kogan, Merav Parter
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph…
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…
Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel
Merav Parter
We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs t…
Õptimal Dual Vertex Failure Connectivity Labels
Merav Parter, Asaf Petruschka
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given -vertex graph , an -VFT (resp., EFT) connectivity l…