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.

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 -