An optimal maximal independent set algorithm for bounded-independence graphs

DOI10.1007/s00446-010-0097-1zbMath1231.68092OpenAlexW1980501142MaRDI 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 algorithmdominating setsymmetry breakingcoloringad hoc networkmaximal matchingconnected dominating setradio networkmaximal independent setsensor networkunit disk graphlocal algorithmbounded-independence graphgrowth bounded graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (13)

Distributed independent sets in interval and segment intersection graphs ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Computing large independent sets in a single round ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Optimal nearest neighbor queries in sensor networks ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems ⋮ Dynamic networks of finite state machines ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed Lower Bounds for Ruling Sets

Cites Work

• Distributed agreement in tile self-assembly
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• A fast and simple randomized parallel algorithm for maximal matching
• Sorting in linear time?
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Coloring unstructured wireless multi-hop networks
• On the locality of bounded growth
• Distributed Computing
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• What cannot be computed locally!

This page was built for publication: An optimal maximal independent set algorithm for bounded-independence graphs