Parallel coloring of graphs: two approximate algorithms

References

• Bauernöppel , F. and Jung , H. 1985 . “ Fast parallel vertex coloring ” . In Lecture Notes in Comput. Sci. , Edited by: Budach , L. Vol. 199 , 28 – 35 . NY : Springer-Verlag .
   Google Scholar
• Boyar , J. and Karloff , H. 1987 . Coloring planar graphs in parallel . J. Algorithms , 8 : 470 – 479 .
   Google Scholar
• Brélaz , D. 1979 . New techniques to color the vertices of a graph . Commun. ACM , 22 : 251 – 256 .
   Web of Science ®Google Scholar
• Chaitan , G. J. , Auslander , M. A. , Chandra , A. K. , Coke , J. , Hopkins , M. E. and Markstein , P. W. 1981 . Register allocation via coloring . Comput. Langs. , 6 : 47 – 57 .
   Google Scholar
• Christofides , N. 1975 . “ chapter 4 ” . In Graph Theory: An Algorithmic Approach , NY : Academic Press .
   Google Scholar
• Diks , K. 1986 . “ A fast parallel algorithm for six-coloring of planar graphs ” . In Lecture Notes in Comput. Sci. , Vol. 233 , 273 – 282 . NY : Springer-Verlag .
   Google Scholar
• Dutton , R. D. and Brigham , R. C. 1981 . A new graph coloring algorithm . Comput. J. , 24 : 85 – 86 .
   Web of Science ®Google Scholar
• Eckstein , D. M. and Alton , D. A. 1977 . Proc. Conf. Theo. Comput. Sci. . Parallel graph processing using depth-first search . 1977 . pp. 21 – 29 .
   Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness , San Francisco : W. H. Freeman and Co. .
   Google Scholar
• Goldberg , A. V. and Plotkin , S. A. 1987 . Parallel (Δ + l)-coloring of constant-degree graphs . Info. Process. Lett. , 25 : 241 – 245 .
   Google Scholar
• Goldberg , A. V. , Plotkin , S. A. and Shannon , G. E. 1987 . Proc. 19th Ann. ACM Symp. Theo. Comput. . Parallel symmetry-breaking in sparse graphs . 1987 . pp. 315 – 325 .
   Google Scholar
• Goldberg , M. K. 1986 . Parallel algorithms for three graph problems . Congressus Numerantium , 54 : 111 – 121 .
   Google Scholar
• Johnson , D. S. 1974 . Approximate algorithms for combinatorial problems . J. Comput. Syst. Sci. , 9 : 256 – 278 .
   Web of Science ®Google Scholar
• Karchmer , M. and Naor , J. 1988 . A fast parallel algorithm to color a graph with Δ colors . J. Algorithms , 9 : 83 – 91 .
   Google Scholar
• Karloff H. J. An NC algorithm for Brooks theorem Manuscript 1986
   Google Scholar
• Luby , M. 1986 . A simple parallel algorithm for the maximal independent set problem . SIAM J. Comput. , 15 : 1036 – 1053 .
   Web of Science ®Google Scholar
• Matula , D. W. , Marble , G. and Isaacson , J. 1972 . “ Graph coloring algorithms ” . In Graph Theory and Computing , Edited by: Read , R. 109 – 122 . NY : Academic Press .
   Google Scholar
• Mitchem , J. 1976 . On various algorithms for estimating the chromatic number of a graph . Comput. J. , 19 : 182 – 183 .
   Google Scholar
• Naor , J. 1987 . A fast parallel coloring of planar graphs with five colors . Info. Process. Lett. , 25 : 51 – 53 .
   Google Scholar
• Shamir , E. and Upfal , E. 1984 . Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces . J. Algorithms , 5 : 488 – 501 .
   Google Scholar
• Syslo , M. M. , Deo , N. and Kowalik , J. S. 1983 . “ chapter 4 ” . In Discrete Optimization Algorithms , NJ : Prentice-Hall .
   Google Scholar
• Walsh , D. J. A. and Powell , M. B. 1967 . An upper bound for the chromatic number and its application to timetabling problem . Comput. J. , 10 : 85 – 86 .
   Google Scholar
• Williams , M. H. and Milne , K. T. 1984 . The performance of algorithms for coloring planar graphs . Comput. J. , 27 : 165 – 170 .
   Google Scholar