A log-star distributed maximal independent set algorithm for growth-bounded graphs

DOI10.1145/1400751.1400758zbMath1301.05341OpenAlexW1997707549MaRDI QIDQ2934330

No author found.

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.1400758

zbMATH Keywords

parallel algorithmssymmetry breakingcoloringad hoc networkssensor networksdominating setslocal algorithmsradio networksunit disk graphsgrowth bounded graphs\textsc{Connected Dominating Sets}\textsc{Maximal Independent Set}

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

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Coloring unstructured radio networks ⋮ Nearly Optimal Local Broadcasting in the SINR Model with Feedback ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Can we locally compute sparse connected subgraphs? ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Distributed approximation of capacitated dominating sets ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Distributed strong diameter network decomposition ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Distributed approximation of cellular coverage ⋮ Beeping a maximal independent set ⋮ Shifting strategy for geometric graphs without geometry ⋮ Leveraging Linial’s Locality Limit ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ On the computation of fixed points in Boolean networks ⋮ Dynamic networks of finite state machines ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Topology Control and Routing in Ad Hoc Networks ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ Distributed backup placement

This page was built for publication: A log-star distributed maximal independent set algorithm for growth-bounded graphs