Distributed (δ+1)-coloring in linear (in δ) time

DOI10.1145/1536414.1536432zbMath1304.05129OpenAlexW2034499376WikidataQ56269082 ScholiaQ56269082MaRDI QIDQ5172704

Michael Elkin, Leonid Barenboim

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.222.3771

zbMATH Keywords

coloringdistributed algorithmsdefective-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items

A fast network-decomposition algorithm and its applications to constant-time distributed computation, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Community detection with the label propagation algorithm: a survey, Can we locally compute sparse connected subgraphs?, Distributed minimum dominating set approximations in restricted families of graphs, Symmetry breaking depending on the chromatic number or the neighborhood growth, Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs, Toward more localized local algorithms: removing assumptions concerning global knowledge, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Combinatorial algorithms for distributed graph coloring, Randomized distributed decision, Distributed \((\varDelta + 1)\)-coloring in the physical model, Distributed deterministic edge coloring using bounded neighborhood independence, Trading Bit, Message, and Time Complexity of Distributed Algorithms, Combinatorial Algorithms for Distributed Graph Coloring, Distributed coloring algorithms for triangle-free graphs