An optimal bit complexity randomized distributed MIS algorithm (extended abstract)

DOI10.1007/978-3-642-11476-2_25MaRDI QIDQ3408183zbMATH OpenOpenAlexFDO

Authors Métivier Yves, Saheb-Djahromi Nasser, John Michael Robson, A. Zemmari

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) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• An optimal bit complexity randomized distributed MIS algorithm
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Distributed Maximal Independent Set using Small Messages
• An Improved Distributed Algorithm for Maximal Independent Set
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Bit complexity of breaking and achieving symmetry in chains and rings
• Communication Complexity
• Design and Analysis of Distributed Algorithms
• Distributed Computing
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Systems
• Introduction to Distributed Algorithms
• Locality in Distributed Graph Algorithms
• On the complexity of distributed graph coloring
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• What Can be Computed Locally?
• What cannot be computed locally!
• \textsc{Maximal Independent Sets} in radio networks

Cited in

(8)

• Tight analysis of parallel randomized greedy MIS
• On lower bounds for the time and the bit complexity of some probabilistic distributed graph algorithms. Extended abstract
• Trading bit, message, and time complexity of distributed algorithms
• Tight bounds for MIS in multichannel radio networks
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• An optimal bit complexity randomized distributed MIS algorithm
• Distributed minimum dominating set approximations in restricted families of graphs
• Luby's MIS algorithms made self-stabilizing

This page was built for publication: An optimal bit complexity randomized distributed MIS algorithm (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3408183)