Distributed Memory Implementation of Bron-Kerbosch Algorithm

doi:10.1109/ACCESS.2024.3393771

2024-01-01

Tejas Ravindra Rote

Murugan Krishnamoorthy *

A. K. Bhatia

Rishu Yadav

S. P. Raja

DOI：10.1109/ACCESS.2024.3393771

原文链接

原文求助

摘要

En 中文

This paper proposes a parallel implementation of the Bron-Kerbosch algorithm, which finds all maximal cliques in large, complex graphs using CPU and thread-level parallelism and distributed memory with multiple cores. With the growing size and complexity of modern graphs, sequential algorithms can become impractical, making parallel computation a promising solution for reducing duration and enhancing scalability. Decomposing the graph into smaller components and distributing the workload across multiple threads using task parallelism is the proposed method. To optimise the algorithm's efficacy across processes, load-balancing techniques are also investigated. The modified Bron-Kerbosch algorithm is implemented and evaluated on a variety of large graphs, exhibiting significant runtime and scalability enhancements over the sequential version. The conclusion of the paper discusses the prospective applications of the parallel Bron-Kerbosch algorithm in a variety of domains, including social network analysis, bio informatics, and network security. Overall, this research contributes to the expanding body of work on parallel computing and graph analysis by emphasising the advantages of CPU and thread-level parallelism for efficiently solving complex computational problems.

Keyword:

Distributed memory

Bron-Kerbosch algorithm

parallel computing

high-performance computing

graph theory

maximal cliques

social network analysis

bio-informatics

network security

performance optimization

scalability