An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)

DOI10.1007/978-3-642-11476-2_25zbMath1274.68683OpenAlexW1886232660MaRDI QIDQ3408183

Saheb-Djahromi Nasser, Métivier Yves, Akka Zemmari, John Michael Robson

Publication date: 24 February 2010

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11476-2_25

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Distributed minimum dominating set approximations in restricted families of graphs, Time-optimal construction of overlay networks, Beeping a maximal independent set, Trading Bit, Message, and Time Complexity of Distributed Algorithms

Cites Work

• Unnamed Item
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Distributed Systems
• Design and Analysis of Distributed Algorithms
• Bit complexity of breaking and achieving symmetry in chains and rings
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Introduction to Distributed Algorithms
• What Can be Computed Locally?
• Communication Complexity
• Maximal independent sets in radio networks
• On the complexity of distributed graph coloring
• Distributed Computing
• What cannot be computed locally!