1 citations · 2 across the 5 of their papers we have counts for
5 papers · 1 filter
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocat…
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…