47 citations · 207 across the 54 of their papers we have counts for
10 papers · 1 filter
Massively Parallel Algorithms for -Matching
Mohsen Ghaffari, Christoph Grunau, Slobodan Mitrović
This paper presents an round massively parallel algorithm for approximation of maximum weighted -matchings, using near-linear memory per machine. Her…
A Nearly Time-Optimal Distributed Approximation of Minimum Cost -Edge-Connected Spanning Subgraph
Michal Dory, Mohsen Ghaffari
The minimum-cost -edge-connected spanning subgraph (-ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While t…
A Cut-Matching Game for Constant-Hop Expanders
Bernhard Haeupler, Jonas Huebotter, Mohsen Ghaffari
This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders. Constant-hop expanders are a s…
Local Computation of Maximal Independent Set
Mohsen Ghaffari
We present a randomized Local Computation Algorithm (LCA) with query complexity for the Maximal Independent Set (MIS) problem. That is, the algorithm determi…
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler +2
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitti…
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour, Mohsen Ghaffari, Christoph Grunau +2
We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of…