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 Article in a 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