Improved distributed degree splitting and edge coloring

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

11 Citations (Scopus)
169 Downloads (Pure)


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 languageEnglish
Title of host publication31st International Symposium on Distributed Computing (DISC 2017)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-3-95977-053-8
Publication statusPublished - 2017
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - Vienna, Austria
Duration: 16 Oct 201720 Oct 2017
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC


  • Distributed Graph Algorithms
  • Degree Splitting
  • Edge Coloring
  • Discrepancy


Dive into the research topics of 'Improved distributed degree splitting and edge coloring'. Together they form a unique fingerprint.

Cite this