×

zbMATH — the first resource for mathematics

Simple distributed \(\Delta+1\)-coloring of graphs. (English) Zbl 1002.68202
Summary: A very natural randomized algorithm for distributed vertex coloring of graphs is analyzed. Under the assumption that the random choices of processors are mutually independent, the execution time will be \(O(\log n)\) rounds almost always. A small modification of the algorithm is also proposed.

MSC:
68W20 Randomized algorithms
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI