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 - Funding Information:
We examine here the average-case parallel complexity of graph coloring problems (which are known to be NP-hard in the worst case). By average case we mean that the inputs are selected randomly from some natural family of distributions parametrized by problem size. We consider two families of random graphs: (a) The class G,,p of graphs of n vertices where each edge may be independently present with probability p (see \[6\]).F or this class of graphs we modify an algorithm of \[4\]a nd do a tight analysis, through which we show that our algorithm colors the input with a number of colors at most twice its chromatic number, in parallel time O(log 4 n~ log log n) by using O(n2p) processors for p = ft((log (a) n)2/log(2) n), on a CRCW PRAM, with probability at least 1 - n -d (d > 1). The algorithm of \[4\]f inds the same number of colors, uses the same number of processors on a CRCW PRAM and runs in O(log 5 n~ log log n) time for p = ft(log n/n), with probabihty at least 1 - O(1/log n). If p < O(log n/n) both algorithms have the same performance on a CRCW PRAM. (b) The class of all k-colorable graphs, for k constant and edge probabihty p = f~(~), where each graph is uniformly chosen. Here the instance is known to h.ave the property we are seeking and *This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM), by the Ministry of Industry, Energy and Technology of Greece and by the NSF grant CCR-89-6949.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
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 -