 |
 |
|
|
Input Description: A graph \(G=(V,E)\).
Problem: What is the largest \(S \subset V\) such that for all \(x,y \in S\), \((x,y) \in E\)?
Excerpt from The Algorithm Design Manual: When I went to high school, everybody complained about the ``clique'', a group of friends who all hung around together and seemed to dominate everything social. Consider a graph whose vertices represent a set of people, with edges between any pair of people who are friends. Thus the clique in high school was in fact a clique in this friendship graph.
Identifying ``clusters'' of related objects often reduces to finding large cliques in graphs. One example is in a program recently developed by the Internal Revenue Service (IRS) to detect organized tax fraud, where groups of phony tax returns are submitted in the hopes of getting undeserved refunds. The IRS constructs graphs with vertices corresponding to submitted tax forms and with edges between any two tax-forms that appear suspiciously similar. A large clique in this graph points to fraud.
| Cliquer (rating 10) |
RAPID (rating 9) |
| GOBLIN (rating 8) |
CAGES (rating 8) |
| quick-cliques (rating 6) |
pmc (rating 6) |
| NetworkX (rating 6) |
Neural-Networks for Cliques and Coloring (rating 5) |
