47 citations · 207 across the 54 of their papers we have counts for
6 papers · 1 filter
Faster Algorithms for Edge Connectivity via Random -Out Contractions
Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each verte…
Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
Mohsen Ghaffari, Julian Portmann
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improv…
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň, Mohsen Ghaffari
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated -time algorithm of Panco…
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
Michal Dory, Mohsen Ghaffari
The minimum-weight -edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has rece…
On the Use of Randomness in Local Distributed Graph Algorithms
Mohsen Ghaffari, Fabian Kuhn
We attempt to better understand randomization in local distributed graph algorithms by exploring how randomness is used and what we can gain from it: - We first ask the question of…
On the Complexity of Distributed Splitting Problems
Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn +2
One of the fundamental open problems in the area of distributed graph algorithms is the question of whether randomization is needed for efficient symmetry breaking. While there are…