@inproceedings{470bb37c3598498fac71b333bbfb7023,
title = "Fast parallel algorithms for coloring random graphs",
abstract = "We improve here the expected performance of parallel algorithms for graph coloring. This is achieved through new adaptive techniques that may be useful for the average-case analysis of many graph algorithms. We apply our techniques to: (a) the class Gn,p of random graphs. We present a parallel algorithm which colors the graph with a number of colors at most twice its chromatic number and runs in time O(log4 n/ log log n) almost surely, for p = Ω((log(3) n)2/ log(2) n). The number of processors used is O(m) where m is the number of edges of the graph. (b) the class of all fc-colorable graphs, uniformly chosen. We present a parallel algorithm which actually constructs the coloring in expected parallel time O(log2 n), for constant k, by using O(m) processors on the average. This problem is not known to have a polynomial time algorithm in the worst case.",
author = "Kedem, {Zvi M.} and Palem, {Krishna V.} and Pantziou, {Grammati E.} and Spirakis, {Paul G.} and Zaroliagis, {Christos D.}",
year = "1992",
doi = "10.1007/3-540-55121-2_13",
language = "English (US)",
isbn = "9783540551218",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "135--147",
editor = "Gunther Schmidt and Rudolf Berghammer",
booktitle = "Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings",
note = "17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 ; Conference date: 17-06-1991 Through 19-06-1991",
}