Abstract:
Maximal clique enumeration is combinatorial graph problem, which identifies the largest fully
connected subgroups within a graph, uncovering tightly-knit communities and critical relationships essential
for analyzing complex networks in social science, biology, and computer science. However, due to its exponen
tial complexity, this combinatorial problem is computationally intensive. The Bron–Kerbosch algorithm is a
popular method for finding maximal cliques, but its sequential execution limits performance on large-scale
graphs. Previous methods mostly focused on GPU-based parallelization (using SIMD and data parallelism)
and distributed memory systems. With the advent of multi-core processors in mainstream devices such
as laptops, tablets, and mobiles, these machines now have the capability to leverage shared-memory par
allelization. Utilizing the parallelism of multi-core hardware offers a promising way to improve execution
efficiency on common platforms. However, prior shared-memory parallelization approaches often involving
SIMD instruction sets and cloud resources, have not sufficiently simplified the parallelization process for
mainstream machines. This study presents parallel implementations of the Bron–Kerbosch algorithm and
its pivot variant using OpenMP, optimized for multi-core shared-memory systems. The parallel algorithms
employ recursive decomposition and load balancing techniques while avoiding race conditions and duplicate
results. Performance was evaluated by varying thread counts and input graph sizes, spanning sparse to
dense graphs. Comparisons between parallel and serial versions on identical hardware demonstrate signifi
cant speedups, with the pivot-based parallel variant showing superior load balancing and reduced redundant
computations. These results confirm that shared-memory parallelism substantially improves scalability and
execution time for maximal clique enumeration, making it a practical approach for large-scale combinatorial
graph problems in mainstream machines.
