47 citations · 104 across the 24 of their papers we have counts for
8 papers · 1 filter
Coloring Fast with Broadcasts
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We present an -round distributed algorithm for the -coloring problem, where each node broadcasts only one -bit message per round to its neighbors…
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a coloring of the graph, where denotes the maximum degree, it suf…
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, Ce Jin
We present round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded…
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…
Distributed Computation in Node-Capacitated Networks
John Augustine, Mohsen Ghaffari, Robert Gmyr +4
In this paper, we study distributed graph algorithms in networks in which the nodes have a limited communication capacity. Many distributed systems are built on top of an underlyin…
Distributed Approximation of Maximum Independent Set and Maximum Matching
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari +1
We present a simple distributed -approximation algorithm for maximum weight independent set (MaxIS) in the model which completes in $O(\texttt{MIS}(G)\cdot \l…