1.5.1 Clique
INPUT OUTPUT
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.
Recommended Books
None Available
Related Links
Neil Sloan's clique page
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
