## 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

Previous slide | Next slide | Back to first slide | View graphic version |