5 papers
Greedy-Like Defective Coloring: Distributed Algorithms and Applications
Marc Fuchs, Fabian Kuhn
A -defective -coloring of a graph is a coloring of the nodes with colors such that every node has at most neighbors of the same color. Distributed algor…
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +3
One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model u…
Distributed -Coloring in Graphs of Bounded Neighborhood Independence
Marc Fuchs, Fabian Kuhn
The distributed coloring problem is arguably one of the key problems studied in the area of distributed graph algorithms. The most standard variant of the problem asks for a proper…
On the Complexity of Distributed Edge Coloring and Orientation Problems
Sebastian Brandt, Fabian Kuhn, Zahra Parsaeian
Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed gra…
Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
Marc Fuchs, Fabian Kuhn
In this paper, we give list coloring variants of simple iterative defective coloring algorithms. Formally, in a list defective coloring instance, each node of a graph is given…