clique - OpenGenus IQ: Learn Algorithms, DL, System Design

Algorithm to find cliques of a given size k【O(n^k) time complexity】

We can find all the 2-cliques by simply enumerating all the edges. To find k+1-cliques, we can use the previous results. Compare all the pairs of k-cliques. If the two subgraphs have k-1 vertices in common and graph contains the missing edge, we can form a k+1-clique.

Algorithms

Greedy approach to find a single maximal clique in O(V^2) time complexity

There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm in O(V^2) time complexity

Algorithms

Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))

Bron–Kerbosch algorithm is an enumeration algorithm for finding maximal cliques in an undirected graph. Any n-vertex graph has at most 3^n⁄3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy) is O(3^n⁄3).

Algorithms

Clique in Graphs

A clique is a subset of vertices of an undirected graph G such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs.