38 citations · 178 across the 46 of their papers we have counts for
7 papers · 1 filter
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…
Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes
Fabian Kuhn, Konstantinos Panagiotou, Pascal Su
We investigate the nearest common ancestor (NCA) function in rooted trees. As the main conceptual contribution, the paper introduces universal trees for the NCA function: For a giv…
Improved Distributed Degree Splitting and Edge Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn +3
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discre…
Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
Abdolhamid Ghodselahi, Fabian Kuhn
The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem…
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…