47 citations · 207 across the 54 of their papers we have counts for
7 papers · 1 filter
Distributed MIS with Low Energy and Time Complexities
Mohsen Ghaffari, Julian Portmann
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy…
A Near-Optimal Deterministic Distributed Synchronizer
Mohsen Ghaffari, Anton Trygub
We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm $\mathca…
Average Awake Complexity of MIS and Matching
Mohsen Ghaffari, Julian Portmann
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is…
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…
Nearly Work-Efficient Parallel DFS in Undirected Graphs
Mohsen Ghaffari, Christoph Grunau, Jiahao Qu
We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any -node -edge undirected grap…
Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari, Christoph Grunau
We present an round deterministic distributed algorithm for the maximal independent set problem. By known reductions, thi…