Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.19
URN: urn:nbn:de:0030-drops-79794
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7979/
Ghaffari, Mohsen ; Hirvonen, Juho ; Kuhn, Fabian ; Maus, Yannic ; Suomela, Jukka ; Uitto, Jara
Improved Distributed Degree Splitting and Edge Coloring
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{ghaffari_et_al:LIPIcs:2017:7979,
author = {Mohsen Ghaffari and Juho Hirvonen and Fabian Kuhn and Yannic Maus and Jukka Suomela and Jara Uitto},
title = {{Improved Distributed Degree Splitting and Edge Coloring}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {19:1--19:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7979},
URN = {urn:nbn:de:0030-drops-79794},
doi = {10.4230/LIPIcs.DISC.2017.19},
annote = {Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy}
}
| Keywords: | Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy | |
| Seminar: | 31st International Symposium on Distributed Computing (DISC 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 12.10.2017 |
