Fast Maximal Cliques Enumeration in Sparse Graphs

In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G=(V,E) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O(Delta (4)) time delay, where Delta is the maximum degree of vertices. However, it requires an O(na <...m) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O(Delta a <...H (3)) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{vaVa pound delta(v)a parts per thousand yenH}|a parts per thousand currency signH given delta(v) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Delta.