TY - GEN
T1 - Fast parallel algorithms for coloring random graphs
AU - Kedem, Zvi M.
AU - Palem, Krishna V.
AU - Pantziou, Grammati E.
AU - Spirakis, Paul G.
AU - Zaroliagis, Christos D.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85029763694&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85029763694&partnerID=8YFLogxK
U2 - 10.1007/3-540-55121-2_13
DO - 10.1007/3-540-55121-2_13
M3 - Conference contribution
AN - SCOPUS:85029763694
SN - 9783540551218
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 135
EP - 147
BT - Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings
A2 - Schmidt, Gunther
A2 - Berghammer, Rudolf
PB - Springer Verlag
T2 - 17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991
Y2 - 17 June 1991 through 19 June 1991
ER -