Coloring fast without learning your neighbors' colors
From MaRDI portal
Publication:6535038
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
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)