Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

DOI10.1016/0196-6774(84)90003-8zbMath0564.05030OpenAlexW2066402549MaRDI QIDQ3677786

Eli Shamir, Eli Upfal

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90003-8

zbMATH Keywords

random graphsdistributed algorithmproper coloringgreedy graph-coloring algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number, Sharp concentration of the chromatic number on random graphs \(G_{n,p}\), Complexity of Coloring Random Graphs, Average-case complexity of backtrack search for coloring sparse random graphs, On the connectivity of proper colorings of random graphs and hypergraphs, On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs, Constraining the clustering transition for colorings of sparse random graphs, The chromatic number of random intersection graphs, The chromatic number of random graphs, Gibbs rapidly samples colorings of \(G(n, d/n)\), Parallel graph algorithms that are efficients on average, A processor efficient MIS algorithm on random graphs