Scalable parallel graph coloring algorithms. (English) Zbl 1008.68565
Summary: Finding a good graph coloring quickly is often a crucial phase in the development of efficient, parallel algorithms for many scientific and engineering applications. In this paper we consider the problem of solving the graph coloring problem itself in parallel. We present a simple and fast parallel graph coloring heuristic that is well suited for shared memory programming and yields an almost linear speedup on the PRAM model. We also present a second heuristic that improves on the number of colors used. The heuristics have been implemented using OpenMP. Experiments conducted on an SGI Cray Origin 2000 supercomputer using very large graphs from finite element methods and eigenvalue computations validate the theoretical run-time analysis.
MSC:
| 68U99 | Computing methodologies and applications |
| 68W10 | Parallel algorithms in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Practical implementations and applications of graph coloring. PhD Thesis, University of Wisconsin-Madison, August 1994. |
| [2] | Gamst, IEEE Transactions of Vehicular Technology 35 pp 8– (1986) · doi:10.1109/T-VT.1986.24063 |
| [3] | Chaitin, Computer Languages 6 pp 47– (1981) · doi:10.1016/0096-0551(81)90048-5 |
| [4] | Garey, IEEE Transactions on Circuits and Systems 23 pp 591– (1976) · Zbl 0342.94021 · doi:10.1109/TCS.1976.1084138 |
| [5] | A comparison of parallel graph coloring algorithms. Technical Report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995. |
| [6] | Coleman, SIAM Journal on Numerical Analysis 20 pp 187– (1983) · Zbl 0527.65033 · doi:10.1137/0720013 |
| [7] | Computers and Intractability. W. H. Freeman: New York, 1979. |
| [8] | A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices (extended abstract). (Lecture Notes in Computer Science, vol. 1541). Springer, 1998; 332-336. |
| [9] | Jones, SIAM Journal of Scientific Computing 14 pp 654– (1993) · Zbl 0772.68046 · doi:10.1137/0914041 |
| [10] | OpenMP. A proposed industry standard api for shared memory programming. http://www.openmp.org/. |
| [11] | Welsh, Computer Journal 10 pp 85– (1967) · Zbl 0147.15206 · doi:10.1093/comjnl/10.1.85 |
| [12] | Brelaz, Communications of the ACM 22 pp 251– (1979) · Zbl 0394.05022 · doi:10.1145/359094.359101 |
| [13] | Grimmet, Mathematical Proceedings of the Cambridge Philosophical Society 77 pp 313– (1975) · Zbl 0297.05112 · doi:10.1017/S0305004100051124 |
| [14] | Luby, SIAM Journal on Computing 15 pp 1036– (1986) · Zbl 0619.68058 · doi:10.1137/0215074 |
| [15] | Gjertsen Jr., Journal of Parallel and Distributed Computing 37 pp 171– (1996) · doi:10.1006/jpdc.1996.0117 |
| [16] | Iterated greedy graph coloring and the difficulty landscape. Technical Report TR 92-07, Department of Computing Science, The University of Alberta, Edmonton, Alberta, Canada, June 1992. |
| [17] | Graph coloring on a coarse grained multiprocessor. Presented at WG 2000, 26th International Workshop on Graph-Theoretic Concepts in Computer Science, 15-17 June 2000, Konstantz, Germany. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
