# Shared-Memory Parallel Maximal Clique Enumeration

arXiv: https://arxiv.org/abs/1807.09417 · HTML: https://mlsanity.com/paper/1807.09417/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)

## Abstract (arXiv)

We present shared-memory parallel methods for Maximal Clique Enumeration (MCE) from a graph. MCE is a fundamental and well-studied graph analytics task, and is a widely used primitive for identifying dense structures in a graph. Due to its computationally intensive nature, parallel methods are imperative for dealing with large graphs. However, surprisingly, there do not yet exist scalable and parallel methods for MCE on a shared-memory parallel machine. In this work, we present efficient shared-memory parallel algorithms for MCE, with the following properties: (1) the parallel algorithms are provably work-efficient relative to a state-of-the-art sequential algorithm (2) the algorithms have a provably small parallel depth, showing that they can scale to a large number of processors, and (3) our implementations on a multicore machine shows a good speedup and scaling behavior with increasing number of cores, and are substantially faster than prior shared-memory parallel algorithms for MCE.