An optimal bit complexity randomized distributed MIS algorithm

DOI10.1007/S00446-010-0121-5MaRDI QIDQ658666zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 6 February 2012

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-010-0121-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Distributed Maximal Independent Set using Small Messages
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• 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?)
• scientific article; zbMATH DE number 5286867 (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
• Coloring unstructured radio networks
• 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!

Cited in

(20)

• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Noisy beeping networks
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• On the microscopic view of time and messages
• Fooling views: a new lower bound technique for distributed computations under congestion
• Brief announcement: Using read-\(k\) inequalities to analyze a distributed MIS algorithm
• Bit complexity of order statistics on a distributed star network
• MIS on trees
• Design patterns in beeping algorithms: examples, emulation, and analysis
• Using read-\(k\) inequalities to analyze a distributed MIS algorithm
• Simple and local independent set approximation
• Tight bounds for MIS in multichannel radio networks
• Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Randomized OBDD-based graph algorithms
• Tight Analysis of Parallel Randomized Greedy MIS
• Randomized OBDD-based graph algorithms
• Luby's MIS algorithms made self-stabilizing
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

This page was built for publication: An optimal bit complexity randomized distributed MIS algorithm

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