About randomised distributed graph colouring and graph partition algorithms

DOI10.1016/J.IC.2010.07.001MaRDI QIDQ710742zbMATH OpenOpenAlexFDO

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

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

zbMATH Keywords

graph partitioncolouringprobabilistic analysisbit complexityrandomised distributed graph algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Simple distributed +1-coloring of graphs
• On the time and the bit complexity of distributed randomised anonymous ring colouring
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Deterministic distributed vertex coloring in polylogarithmic time
• Deterministic distributed vertex coloring in polylogarithmic time

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Bit complexity of breaking and achieving symmetry in chains and rings
• Design and Analysis of Distributed Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Dynamical sources in information theory: A general analysis of trie structures
• Fast distributed network decompositions and covers
• Locality in Distributed Graph Algorithms
• Low diameter graph decompositions
• On the complexity of distributed graph coloring
• Peaks and Eulerian numbers in a random sequence
• Simple and efficient network decomposition and synchronization
• Simple distributed \(\Delta+1\)-coloring of graphs
• Sublinear fully distributed partition with applications
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case

Cited in

(7)

• 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
• The influence of random number generators on graph partitioning algorithms
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

This page was built for publication: About randomised distributed graph colouring and graph partition algorithms

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