Distributed Graph Coloring: Fundamentals and Recent Developments

DOI10.2200/S00520ED1V01Y201307DCT011zbMath1310.68004MaRDI QIDQ4980035

Michael Elkin, Leonid Barenboim

Publication date: 20 June 2014

Published in: Synthesis Lectures on Distributed Computing Theory (Search for Journal in Brave)

zbMATH Keywords

colouringrandomized algorithmmaximal matchingdeterministic algorithmarboricitymaximal independent setdistributed symmetry breaking

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (44)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Simple Distributed Δ + 1 Coloring in the SINR Model ⋮ Nearly Optimal Local Broadcasting in the SINR Model with Feedback ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ A fast distributed algorithm for \((\Delta+1)\)-edge-coloring ⋮ Distributed algorithms for random graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Locally checkable problems in rooted trees ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Lower bound for constant-size local certification ⋮ A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ A hierarchy of local decision ⋮ Improved distributed \(\Delta\)-coloring ⋮ Price of anarchy for graph coloring games with concave payoff ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Equilibria of Games in Networks for Local Tasks ⋮ Distributed Recoloring ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed backup placement ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Improved Dynamic Graph Coloring ⋮ Local mending ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Introduction to local certification ⋮ Distributed algorithms for fractional coloring

This page was built for publication: Distributed Graph Coloring: Fundamentals and Recent Developments