12 citations · 29 across the 37 of their papers we have counts for
5 papers · 1 filter
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…
Streaming Edge Coloring with Asymptotically Optimal Colors
Soheil Behnezhad, Mohammad Saneian
Given a graph , an edge-coloring is an assignment of colors to edges of such that any two edges sharing an endpoint receive different colors. By Vizing's celebrated theorem,…
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation
Amir Azarmehr, Soheil Behnezhad
We study the robust communication complexity of maximum matching. Edges of an arbitrary -vertex graph are randomly partitioned between Alice and Bob independently and unifor…
Sublinear Algorithms for TSP via Path Covers
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related {\em maximum path cover} problem, which asks for a collection of…