Improved distributed degree splitting and edge coloring

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-15
Series
31st International Symposium on Distributed Computing (DISC 2017, Leibniz International Proceedings in Informatics (LIPIcs), Volume 91
Abstract
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 present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.
Description
Keywords
Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy
Other note
Citation
Ghaffari, M, Hirvonen, J, Kuhn, F, Maus, Y, Suomela, J & Uitto, J 2017, Improved distributed degree splitting and edge coloring . in 31st International Symposium on Distributed Computing (DISC 2017) ., 19, Leibniz International Proceedings in Informatics (LIPIcs), vol. 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-15, International Symposium on Distributed Computing, Vienna, Austria, 16/10/2017 . https://doi.org/10.4230/LIPIcs.DISC.2017.19