Graph Coloring Algorithm Using CUDA
Zach Burnside · ScholarWorks - GVSU (Grand Valley State University) · 2013
Graphs are mathematical entities that can be used to model many real life systems. Graphs consist of nodes (circles) and edges that join those nodes. A classical problem in graph theory is the coloring problem. Given a particular graph, what is the minimum number of colors that are required to color the nodes of the graph if we do not want two nodes that are connected to have the same color? This problem is very difficult (time consuming) to solve. An exact algorithm to solve this problem using Graphical Processing Units (GPUs) will be described. The algorithm will work for small graphs. Performance results for some well-known graphs will be presented.