Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

DOI10.1145/1400751.1400757zbMath1301.05327OpenAlexW1987125980MaRDI QIDQ2934329

Michael Elkin, Leonid Barenboim

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1400751.1400757

zbMATH Keywords

coloringarboricityMIS\textsc{Maximal Independent Set}forests decomposition

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) 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, Symmetry breaking depending on the chromatic number or the neighborhood growth, Distributed Graph Algorithms and their Complexity: An Introduction, Combinatorial algorithms for distributed graph coloring, On the complexity of distributed graph coloring with local minimality constraints, Distributed deterministic edge coloring using bounded neighborhood independence, Combinatorial Algorithms for Distributed Graph Coloring