Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2018

Journal or Book Title

arXiv

Abstract

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.

Comments

This is a manuscript published as Das, Apurba, Seyed-Vahid Sanei-Mehri, and Srikanta Tirthapura. "Shared-Memory Parallel Maximal Clique Enumeration." arXiv preprint arXiv:1807.09417 (2018).

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS