Coloring fast without learning your neighbors' colors

DOI10.4230/LIPICS.DISC.2020.39zbMATH Open1540.68182MaRDI QIDQ6535038

Fabian Kuhn, Alexandre Nolin, Magnús M. Halldórsson, Yannic Maus

Publication date: 2 November 2023

zbMATH Keywords

congestiondistance-2 coloringdistributed graph coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Cites Work

• Simple distributed \(\Delta+1\)-coloring of graphs
• Derandomizing local distributed algorithms under bandwidth restrictions
• Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
• The Locality of Distributed Symmetry Breaking
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An algorithmic approach to the Lovász local lemma. I
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Deterministic distributed vertex coloring in polylogarithmic time
• On the complexity of distributed graph coloring
• Locally-Iterative Distributed (Δ+ 1)
• An optimal distributed (Δ+1)-coloring algorithm?
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Distributed Maximal Independent Set using Small Messages
• (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Distributed Approximation on Power Graphs
• Distance-2 Coloring in the CONGEST Model
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The coloring game on matroids 👍 👎
• Colorings at minimum cost 👍 👎
• Coloring tournaments: from local to global 👍 👎
• Coloring With a Limited Paintbox 👍 👎
• Superfast coloring in CONGEST via efficient color sampling 👍 👎
• Superfast coloring in CONGEST via efficient color sampling 👍 👎

This page was built for publication: Coloring fast without learning your neighbors' colors

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