Experimental analysis of simple, distributed vertex coloring algorithms

ABSTRACT

We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for (Δ + 1)- and so-called Brooks-Vizing vertex colorings, i.e., colorings using considerably fewer than Δ colors. We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms w.r.t. the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms are extremely fast and very effective, thus being amenable to be used in practice.

REFERENCES

• 1: J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin. A Comparison of Parallel Graph Coloring Algorithms. Technical Report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995.
• 2: S. Basagni, Finding a maximal weighted independent set in wireless networks, Telecommunication Systems, 18:1,2, 155-168, 2001.
• 3: B. Bollobás. Chromatic number, girth, and maximal degree. Discrete Mathematics 24:311-314, 1978.
• 4: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 5: Shiva Chaudhuri , Devdatt Dubhashi, Probabilistic recurrence relations revisited, Theoretical Computer Science, v.181 n.1, p.45-56, July 15, 1997 [doi>10.1016/S0304-3975(96)00261-7 ]
• 6: T. F. Coleman and J. J. Moré. Estimation of Sparse Jacobian Matrices and Graph Coloring Problems. SIAM Journal on Numerical Analysis, 20:187-209, 1983.
• 7: J. C. Culberson. http://web.cs.ualberta.ca/~joe/Coloring/.
• 8: FTP site of DIMACS implementation challenges. ftp://dimacs.rutgers.edu/pub/challenge/.
• 9: A. H. Gebremedhin and F. Manne. Scalable Parallel Graph Coloring Algorithms. Concurrency: Practice and Experience, 12:1131-1146, 2000.
• 10: David A. Grable , Alessandro Panconesi, Fast distributed algorithms for Brooks-Vizing colorings, Journal of Algorithms, v.37 n.1, p.85-120, Oct. 2000 [doi>10.1006/jagm.2000.1097 ]
• 11: David A. Grable , Alessandro Panconesi, Nearly optimal distributed edge coloring in O(log log n) rounds, Random Structures & Algorithms, v.10 n.3, p.385-405, May 1997 [doi>10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-S ]
• 12: G. R. Grimmet and C. J. H. McDiarmid. On Colouring Random Graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77:313-324, 1975.
• 13: David J. Johnson , Michael A. Trick, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993, American Mathematical Society, Boston, MA, 1996
• 14: A. R. Johansson. Asymptotic choice number for triangle-free graphs. Preprint, DIMACS, September 30, 1996.
• 15: Öjvind Johansson, Simple distributed&Dgr; + 1-coloring of graphs, Information Processing Letters, v.70 n.5, p.229-232, June 21, 1999 [doi>10.1016/S0020-0190(99)00064-2 ]
• 16: Mark T. Jones , Paul E. Plassmann, A parallel graph coloring heuristic, SIAM Journal on Scientific Computing, v.14 n.3, p.654-669, May 1993 [doi>10.1137/0914041]
• 17: Richard M. Karp, Probabilistic recurrence relations, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.190-197, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103443]
• 18: J. H. Kim, On Brooks' Theorem for sparse graphs, Combinatorics Probability and Computing, 4 (1995) 97-132.
• 19: J. Körner. Private communication.
• 20: G. Lewandowski and A. Condon. Experiments with Parallel Graph Coloring Heuristics and Applications of Graph Coloring. Cliques, Coloring, and Satisfiability, volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996.
• 21: Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993 [doi>10.1016/0022-0000(93)90033-S]
• 22: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 23: Madhav V. Marathe , Alessandro Panconesi , Larry D. Risinger, An experimental study of a simple, distributed edge coloring algorithm, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.166-175, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341820]
• 24: P. Sinha, R. Sivakumar, and V. Bharghavan, Enhancing ad hoc routing with dynamical virtual infrastructures, Proceedings of IEEE Infocom 2001, 1-10.
• 25: P. Sinha, R. Sivakumar, and V. Bharghavan, CEDAR: a core-extraction distributed ad-hoc routing algorithms, IEEE Journal on Selected Areas in Communication, 17, 8, 1454-1458, August 1999.