Fast Algorithms for Enumerating Cliques in Huge Graphs
Takeaki Uno · 2003
A vertex subset of a graph G = (V, E) is called a clique if any two vertices of S are connected by an edge. A vertex subset of a bipartite graph G = (V1 ∪ V2, E) is called a bipartite clique if any two vertices v1 ∈ V1 and v2 ∈ V2 are connected by an edge. In this paper, we propose a practical fast enumeration algorithm for maximal cliques and bipartite maximal cliques of huge sparse graphs. The time complexity per maximal clique is reduced from O(|V ||E|) to O(∆), and that of maximal bipartite cliques is reduced from O(|V ||E|) to O(∆). By computational experiments, we show that the algorithm takes O(∆) in random instances, and the computation time is very short for some real world problems.