47 citations · 108 across the 28 of their papers we have counts for
6 papers · 2 filters
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus +1
We present a deterministic distributed algorithm, in the LOCAL model, that computes a -edge-coloring in polylogarithmic-time, so long as the maximum degree $Δ=\tildeΩ(\l…
On Derandomizing Local Distributed Algorithms
Mohsen Ghaffari, David G. Harris, Fabian Kuhn
The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithm…
Simple and Near-Optimal Distributed Coloring for Sparse Graphs
Mohsen Ghaffari, Christiana Lymouri
Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with colors, where denotes the m…
Sublogarithmic Distributed Algorithms for Lovász Local lemma, and the Complexity Hierarchy
Manuela Fischer, Mohsen Ghaffari
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of distributed algorithms. In a recent enlightening revelation, Chang and Pe…
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
We present a deterministic distributed algorithm that computes a -edge-coloring, or even list-edge-coloring, in any -node graph with maximum degree , in $O(\log^7 Δ\l…
Simplified and Space-Optimal Semi-Streaming for -Approximate Matching
Mohsen Ghaffari, David Wajc
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass ()-approximation algorithm for the maximum weight matching problem in the semi-streaming model.…