COMP 5704: Parallel Algorithms and Applications in Data Science

School of Electrical Engineering and Computer Science
University of Ottawa, Ottawa, Canada

Project Title: A Round-Based Approach to Distributed Graph Coloring and Comparison to Other Methods

Name: David Worley

E-Mail: dworl020 at uottawa .ca

Project Outline: The first stage of my project is to present a literature review and comparison of current state-of-the-art methodologies for distributed graph coloring. The second stage will be to implement one such algorithm, recently designed by Maus. This is a round based algorithm where each of the p processors will process n/p vertices and generate a sequence for them. This sequence is calculated by sampling distinct polynomials from a prime field to guarantee minimal conflicts between any two polynomials. With this, vertices can test the colors in their sequence for conflicts with their neighbour and permanently color themselves once they have found a more suitable color. This algorithm scales between generating a Δ + 1 coloring and a O(Δ^2) coloring, subsuming many prevalent distributed graph coloring algorithms through clever choice of parameters. Experimental coloring results will be discussed for graphs of increasing size.

Startup Paper(s): Maus, Y. (2021). Distributed Graph Coloring Made Easy. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures.


Relevant References: