  Maximal Clique Enumeration (MCE) is a fundamental graph mining problem, and
is useful as a primitive in identifying dense structures in a graph. Due to the
high computational cost of MCE, parallel methods are imperative for dealing
with large graphs. We present 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 they can scale to a
large number of processors, and (3) our implementations on a multicore machine
show good speedup and scaling behavior with increasing number of cores, and are
substantially faster than prior shared-memory parallel algorithms for MCE; for
instance, on certain input graphs, while prior works either ran out of memory
or did not complete in 5 hours, our implementation finished within a minute
using 32 cores. We also present work-efficient parallel algorithms for
maintaining the set of all maximal cliques in a dynamic graph that is changing
through the addition of edges.
