Distributed (δ+1)-coloring in linear (in δ) time
From MaRDI portal
Publication:5172704
DOI10.1145/1536414.1536432zbMath1304.05129WikidataQ56269082 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
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W15: Distributed algorithms
Related Items
Distributed deterministic edge coloring using bounded neighborhood independence, Distributed minimum dominating set approximations in restricted families of graphs, Symmetry breaking depending on the chromatic number or the neighborhood growth, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Distributed \((\varDelta + 1)\)-coloring in the physical model, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Community detection with the label propagation algorithm: a survey, Combinatorial algorithms for distributed graph coloring, Randomized distributed decision, Distributed coloring algorithms for triangle-free graphs, Can we locally compute sparse connected subgraphs?, Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs, Toward more localized local algorithms: removing assumptions concerning global knowledge, Trading Bit, Message, and Time Complexity of Distributed Algorithms, Combinatorial Algorithms for Distributed Graph Coloring, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
