12 citations · 29 across the 37 of their papers we have counts for
4 papers · 2 filters
Fully Dynamic Matching: Beating 2-Approximation in Update Time
Soheil Behnezhad, Jakub Łącki, Vahab Mirrokni
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and de…
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +2
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…