Clique Detection
An inherently NP-complete problem that is normally approached using approaches based on clique detection
A clique is a set of mutually adjacent nodes in a graph
- A maximal clique is a clique that isn’t a subgraph of a larger clique
- A maximum clique is the largest maximal clique
A correspondence graph (or modular product graph) between two graphs, G1 and G2, is a graph
- In which the nodes are pairs of nodes, one from G1 and one from G2 , e.g. {G1(I), G2(J)} and {G1(K), G2(L)}
- In which there is an edge if the edge connecting G1(I) to G1(K) is the same as that connecting G2(J) to G2(L)
A maximum clique in this correspondence graph is the maximum common subgraph (MCS) between G1 and G2