An optimal maximal independent set algorithm for bounded-independence graphs

DOI10.1007/s00446-010-0097-1zbMath1231.68092MaRDI QIDQ992507

J. Martínez

Publication date: 9 September 2010

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/157549

zbMATH Keywords

parallel algorithm; dominating set; symmetry breaking; coloring; ad hoc network; maximal matching; connected dominating set; radio network; maximal independent set; sensor network; unit disk graph; local algorithm; bounded-independence graph; growth bounded graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68M14: Distributed systems

68W15: Distributed algorithms