1 citations · 2 across the 3 of their papers we have counts for
3 papers
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a ver…
Fully Dynamic Matching: -Approximation in Polylog Update Time
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
We study maximum matchings in fully dynamic graphs, which are graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum m…
Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a -approximation algorithm which can be implemented…