Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 26, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jara Uitto
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 discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We consider the LOCAL model of distributed message passing and present simple and fast deterministic distributed algorithms for both variants. This also leads to a deterministic algorithm for $(2+o(1))\Delta$-edge-coloring.
Automatic MiSe System Software Version 1.4803M | admin login