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.
Original language | English |
---|---|
Title of host publication | 31st International Symposium on Distributed Computing (DISC 2017) |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 1-15 |
ISBN (Electronic) | 978-3-95977-053-8 |
DOIs | |
Publication status | Published - 2017 |
MoE publication type | A4 Conference publication |
Event | International Symposium on Distributed Computing - Vienna, Austria Duration: 16 Oct 2017 → 20 Oct 2017 Conference number: 31 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl--Leibniz-Zentrum für Informatik |
Volume | 91 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | International Symposium on Distributed Computing |
---|---|
Abbreviated title | DISC |
Country/Territory | Austria |
City | Vienna |
Period | 16/10/2017 → 20/10/2017 |
Keywords
- Distributed Graph Algorithms
- Degree Splitting
- Edge Coloring
- Discrepancy