An optimal bit complexity randomized distributed MIS algorithm
DOI10.1007/S00446-010-0121-5zbMATH Open1231.68277DBLPjournals/dc/MetivierRSZ11OpenAlexW2149652607WikidataQ59409896 ScholiaQ59409896MaRDI QIDQ658666FDOQ658666
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
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
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Introduction to Distributed Algorithms
- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
- Title not available (Why is that?)
- Design and Analysis of Distributed Algorithms
- Bit complexity of breaking and achieving symmetry in chains and rings
- Distributed Computing: A Locality-Sensitive Approach
- Communication Complexity
- 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
- What cannot be computed locally!
- On the complexity of distributed graph coloring
- Distributed Computing
- What Can be Computed Locally?
- Coloring unstructured radio networks
- Distributed Systems
- Title not available (Why is that?)
Cited In (20)
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- On the microscopic view of time and messages
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Noisy beeping networks
- 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
- Find Your Place: Simple Distributed Algorithms for Community Detection
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Tight Analysis of Parallel Randomized Greedy MIS
- Randomized OBDD-based graph algorithms
- 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)
