38 citations · 178 across the 46 of their papers we have counts for
7 papers · 1 filter
Efficient Deterministic Distributed Coloring with Small Bandwidth
Philipp Bamberger, Fabian Kuhn, Yannic Maus
We show that the -list coloring problem can be solved deterministically in rounds in the \CONGEST model, where is the diameter of t…
Shortest Paths in a Hybrid Network Model
John Augustine, Kristian Hinnenthal, Fabian Kuhn +2
We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where communication is only possible between spec…
Faster Deterministic Distributed Coloring Through Recursive List Coloring
Fabian Kuhn
We provide novel deterministic distributed vertex coloring algorithms. As our main result, we give a deterministic distributed algorithm to compute a -coloring of an -nod…
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…
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
Janosch Deurer, Fabian Kuhn, Yannic Maus
We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For $ε>1/{\text{poly}}…