Improved distributed degree splitting and edge coloring

DOI10.1007/S00446-018-00346-8zbMATH Open1445.68336arXiv1706.04746OpenAlexW3101102136MaRDI QIDQ2189174FDOQ2189174

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)