Improved distributed degree splitting and edge coloring

DOI10.1007/S00446-018-00346-8MaRDI QIDQ2189174zbMATHOpenAlexFDO

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

Publication date 15 June 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.04746

zbMATH Keywords

discrepancyedge coloringdistributed graph algorithmsdegree splitting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

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.

Recommendations

• Improved distributed degree splitting and edge coloring
• Distributed degree splitting, edge coloring, and orientations
• Deterministic distributed edge-coloring with fewer colors
• \((2\Delta-1)\)-edge-coloring is much easier than maximal matching in the distributed setting
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring

Cites work

• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1875427 (Why is no real title available?)
• A lower bound for the distributed Lovász local lemma
• A note on the Beck-Fiala theorem
• An improved parallel algorithm for maximal matching
• An improvement of the Beck-Fiala theorem
• Deterministic distributed edge-coloring with fewer colors
• Distributed Computing: A Locality-Sensitive Approach
• Distributed degree splitting, edge coloring, and orientations
• Distributed deterministic edge coloring using bounded neighborhood independence
• Efficient parallel algorithms for edge coloring problems
• Improved distributed degree splitting and edge coloring
• On the distributed complexity of computing maximal matchings
• Some simple distributed algorithms for sparse networks
• What can be computed locally?
• ``Integer-making theorems

Cited in

(6)

• Network Decomposition and Distributed Derandomization (Invited Paper)
• Improved distributed degree splitting and edge coloring
• Linial for lists
• Distributed degree splitting, edge coloring, and orientations
• Distributed dense subgraph detection and low outdegree orientation
• Local conflict coloring revisited: Linial for lists

This page was built for publication: Improved distributed degree splitting and edge coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189174)