Deterministic distributed edge-coloring with fewer colors

DOI10.1145/3188745.3188906MaRDI QIDQ5230307zbMATH OpenOpenAlexWikidataFDO

Authors Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

deterministicdistributed computingedge-coloringmatchingmatching approximationVizing's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Abstract: We present a deterministic distributed algorithm, in the LOCAL model, that computes a $(1+o(1))Delta$-edge-coloring in polylogarithmic-time, so long as the maximum degree $Delta=ildeOmega(logn)$. For smaller $Delta$, we give a polylogarithmic-time $3Delta/2$-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of $2Delta-1$ colors, and they improve significantly on the recent polylogarithmic-time $(2Delta-1)(1+o(1))$-edge-coloring of Ghaffari and Su [SODA'17] and the $(2Delta-1)$-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS'17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

Recommendations

• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• (2-1)-edge-coloring is much easier than maximal matching in the distributed setting
• Towards the locality of Vizing's theorem
• Distributed deterministic edge coloring using bounded neighborhood independence
• Distributed deterministic edge coloring using bounded neighborhood independence

Cited in

(30)

• Near-optimal, distributed edge colouring via the nibble method
• Linial for lists
• Improved distributed degree splitting and edge coloring
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• Distributed degree splitting, edge coloring, and orientations
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• scientific article; zbMATH DE number 1875427 (Why is no real title available?)
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Coloring in Sparse Graphs with Fewer Colors
• Towards the locality of Vizing's theorem
• (2-1)-edge-coloring is much easier than maximal matching in the distributed setting
• Deterministic distributed \((\Delta + o(\Delta))\)-edge-coloring, and vertex-coloring of graphs with bounded diversity
• Distributed deterministic edge coloring using bounded neighborhood independence
• Distributed deterministic edge coloring using bounded neighborhood independence
• Near-optimal distributed edge coloring
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Improved distributed degree splitting and edge coloring
• The power of multi-step Vizing chains
• Local conflict coloring revisited: Linial for lists
• Borel Vizing's theorem for graphs of subexponential growth
• Sparsity-parameterised dynamic edge colouring
• Fast algorithms for Vizing's theorem on bounded degree graphs
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Vizing's theorem in near-linear time
• Improved streaming edge coloring

This page was built for publication: Deterministic distributed edge-coloring with fewer colors

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