Practical Multi-threaded Graph Coloring Algorithms for Shared Memory Architecture

Singhal, N and Peri, Sathya and Kalyanasundaram, Subrahmanyam (2017) Practical Multi-threaded Graph Coloring Algorithms for Shared Memory Architecture. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, January 05 - 07, 2017, Hyderabad, India.

Full text not available from this repository. (Request a copy)

Abstract

In this paper, we present multi-threaded algorithms for graph coloring suitable to the shared memory programming model. Initially, we describe shared memory implementations to the algorithms widely known in the literature like Jones Plassman graph coloring. Later, we propose new approaches to solve the problem of coloring using mutex locks while making sure that deadlocks do not occur. Using datasets from real world graphs, we evaluate the performance of all these algorithms on the Intel platform. We compare the performance of sequential graph coloring v/s our proposed approaches and analyze the speedup obtained against the existing algorithms from the literature. The results show that the speedup obtained by our proposed algorithms in terms of the time taken for coloring is consequential. We also provide a direction for future work towards improving the performance further in terms of different metrics.

[error in script]

IITH Creators: