Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 10, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Sebastian Brandt
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the recent "half-edge labeling" formalism. Examples of binary labeling problems include regular versions of sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode, e.g., any cardinality constraints on indegrees and outdegrees.
We show that, in the LOCAL model, the complexity of any such problem is either constant, logarithmic, or linear, or the problem is unsolvable. Furthermore, we show that the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.
Automatic MiSe System Software Version 1.4803M | admin login