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

Improved distributed degree splitting and edge coloring

DISC 2017 · 31st International Symposium on Distributed Computing, Vienna, Austria, October 2017 · doi:10.4230/LIPIcs.DISC.2017.19

DISC 2017 Best Paper Award

authors’ version publisher’s version


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.


Andréa W. Richa (Ed.): 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:15, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017

ISBN 978-3-95977-053-8

Journal Version

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.