Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Fast parallel algorithms for coloring random graphs

  • Conference paper
  • First Online:

Abstract

We improve here theexpected performance of parallel algorithms for graph coloring. This is achieved through newadaptive techniques that may be useful for the average-case analysis of many graph algorithms. We apply our techniques to:

  1. (a)

    the classGn,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(log4n/ log logn) almost surely, forp = Ω((log(3)n)2/ log(2)n). The number of processors used is O(m) wherem is the number of edges of the graph.

  2. (b)

    the class of allk-colorable graphs, uniformly chosen. We present a parallel algorithm which actuallyconstructs the coloring inexpected parallel time O(log2n), for constantk, by using O(m) processors on the average. This problem is not known to have a polynomial time algorithm in the worst case.

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.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. B. Bollobas, “Random Graphs”, Academic Press, London, 1985.

    Google Scholar 

  2. H. Chernoff, “A measure of asymptotic efficiency for tests based on the sum of observations”,Ann. Math. Statist. 23 (1952), 493–509.

    Google Scholar 

  3. A. Calkin, A. Frieze, “Probabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets”,Random Structures & Algorithms, Vol.1, No.l, 39–50, 1990.

    Google Scholar 

  4. D. Coppersmith, P. Raghavan, M. Tompa, “Parallel Graph Algorithms that are Efficient on Average”,Proc. of the 28th Annual IEEE FOCS, 1987, pp.260–269.

    Google Scholar 

  5. M. E. Dyer, A. M. Frieze, “The Solution of Some Random NP-hard Problems in Polynomial Expected Time”,Journal of Algorithms, 10, 451–489, 1989.

    Google Scholar 

  6. P. Erdos, A. Renyi, “On random graphs I”,Publ. Math. Debrecen, 6 (1959), 290–297.

    Google Scholar 

  7. Z. Kedem, K. Palem, P. Spirakis, “Adaptive average case analysis”, unpublished manuscript, 1990.

    Google Scholar 

  8. L. Kucera, “Expected behaviour of graph coloring algorithms”,Proc. of Fundamentals in Computation Theory LNCS, Vol.56, pp.447–451, Springer-Verlag, 1977.

    Google Scholar 

  9. J.E. Littlewood, “On the probability in the tail of a binomial distribution”,Adv. Appl. Probab., 1(1969), 43–72.

    Google Scholar 

  10. G. Pantziou, P. Spirakis, C. Zaroliagis, “Coloring Random Graphs Efficiently in Parallel, through Adaptive Techniques”, CTI TR-90.10.25, Computer Technology Institute, Patras. Also presented in the ALCOM Workshop on Graph Algorithms, Data Structures and Computational Geometry, Berlin 3–5 October, 1990.

    Google Scholar 

  11. J. Spencer, “Ten Lectures on the Probabilistic Method”, SIAM, 1987.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept of Computer Science, Courant Institute of Math. Sciences NYU, 251 Mercer St, 10012, New York, NY, USA

    Zvi M. Kedem & Paul G. Spirakis

  2. IBM Research Division, T.J. Watson Research Center, P.O. Box 704, 10598, Yorktown Heights, NY, USA

    Krishna V. Palem

  3. Computer Technology Institute, P.O. Box 1122, 26110, Patras, Greece

    Grammati E. Pantziou, Paul G. Spirakis & Christos D. Zaroliagis

  4. Computer Sc and Eng Dept, University of Patras, Greece

    Paul G. Spirakis & Christos D. Zaroliagis

Authors
  1. Zvi M. Kedem

    You can also search for this author inPubMed Google Scholar

  2. Krishna V. Palem

    You can also search for this author inPubMed Google Scholar

  3. Grammati E. Pantziou

    You can also search for this author inPubMed Google Scholar

  4. Paul G. Spirakis

    You can also search for this author inPubMed Google Scholar

  5. Christos D. Zaroliagis

    You can also search for this author inPubMed Google Scholar

Editor information

Gunther Schmidt Rudolf Berghammer

Rights and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kedem, Z.M., Palem, K.V., Pantziou, G.E., Spirakis, P.G., Zaroliagis, C.D. (1992). Fast parallel algorithms for coloring random graphs. In: Schmidt, G., Berghammer, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 1991. Lecture Notes in Computer Science, vol 570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55121-2_13

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp