About randomised distributed graph colouring and graph partition algorithms
From MaRDI portal
Publication:710742
DOI10.1016/j.ic.2010.07.001zbMath1204.68272OpenAlexW2062111496MaRDI QIDQ710742
Akka Zemmari, Nasser Saheb-Djahromi, John Michael Robson, Yves Métivier
Publication date: 22 October 2010
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.07.001
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (5)
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 ⋮ On the time and the bit complexity of distributed randomised anonymous ring colouring ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
Cites Work
- Unnamed Item
- Fast distributed network decompositions and covers
- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
- Low diameter graph decompositions
- Simple and efficient network decomposition and synchronization
- Simple distributed \(\Delta+1\)-coloring of graphs
- Dynamical sources in information theory: A general analysis of trie structures
- Sublinear fully distributed partition with applications
- Design and Analysis of Distributed Algorithms
- Bit complexity of breaking and achieving symmetry in chains and rings
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Peaks and Eulerian numbers in a random sequence
- On the complexity of distributed graph coloring
This page was built for publication: About randomised distributed graph colouring and graph partition algorithms
