CLUSTER Algorithm Design: Picking Cluster Representatives

Picking Cluster Representatives:

The last step in CLUSTER is to pick the minimum number of representatives R from the list of all maximal cliques such that every vertex in V\R is connected to at least one vertex in R. Since the number of cliques in a graph of size n is 𝑂(3^𝑛/3), using a brute force algorithm would not be feasible. Thus, I applied a heuristic where from a list of all possible candidates CAND (initially, it contains all nodes) we keep picking the vertex included in the highest number of cliques as a representative rep, remove from CAND all the nodes contained in the clusters where rep exists, then repeat until no nodes are left in CAND.