Fast parallel algorithms for coloring random graphs

Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings
EditorsGunther Schmidt, Rudolf Berghammer
PublisherSpringer Verlag
Pages135-147
Number of pages13
ISBN (Print)9783540551218
DOIs
StatePublished - 1992
Event17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991 - Fischbachau, Germany
Duration: Jun 17 1991Jun 19 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume570 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1991
CountryGermany
CityFischbachau
Period6/17/916/19/91

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast parallel algorithms for coloring random graphs'. Together they form a unique fingerprint.

  • Cite this

    Kedem, Z. M., Palem, K. V., Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C. D. (1992). Fast parallel algorithms for coloring random graphs. In G. Schmidt, & R. Berghammer (Eds.), Graph-Theoretic Concepts in Computer Science - 17th International Workshop, WG 1991, Proceedings (pp. 135-147). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 570 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-55121-2_13