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 (16)

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

This page was built for publication: Distributed (δ+1)-coloring in linear (in δ) time