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)


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:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 10 Jan 2017 04:13
Last Modified: 20 Sep 2017 08:59
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2974 Statistics for this ePrint Item