Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
From MaRDI portal
Publication:391647
DOI10.1016/J.IC.2013.10.005zbMath1358.68222OpenAlexW2151519507MaRDI QIDQ391647
John Michael Robson, Akka Zemmari, Allyx Fontaine, Yves Métivier
Publication date: 10 January 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2013.10.005
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (2)
Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
Cites Work
- Unnamed Item
- An optimal bit complexity randomized distributed MIS algorithm
- About randomised distributed graph colouring and graph partition algorithms
- A fast and simple randomized parallel algorithm for maximal matching
- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
- Simple distributed \(\Delta+1\)-coloring of graphs
- On the Distributed Complexity of Computing Maximal Matchings
- On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph 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
- Maximal independent sets in radio networks
- On the complexity of distributed graph coloring
- Distributed Computing
This page was built for publication: Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
