2026-07-22T12:14:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7979 2024-03-06T10:41:39Z ddc:004 open_access

Improved Distributed Degree Splitting and Edge Coloring Ghaffari, Mohsen Hirvonen, Juho Kuhn, Fabian Maus, Yannic Suomela, Jukka Uitto, Jara Distributed Graph Algorithms Degree Splitting Edge Coloring Discrepancy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohsen Ghaffari and Juho Hirvonen and Fabian Kuhn and Yannic Maus and Jukka Suomela and Jara Uitto 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.19 urn:nbn:de:0030-drops-79794 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode