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 contributionScientificpeer-review

8 Citations (Scopus)
97 Downloads (Pure)

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 languageEnglish
Title of host publication31st International Symposium on Distributed Computing (DISC 2017)
Pages1-15
ISBN (Electronic)978-3-95977-053-8
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a 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
Volume91
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CountryAustria
CityVienna
Period16/10/201720/10/2017

Keywords

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

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

Cite this