History
Although complete subgraphs have been studied for longer in mathematics, the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. The "clique" terminology comes from Luce & Perry (1949), and the first algorithm for solving the clique problem is that of Harary & Ross (1957), who were motivated by the sociological application.
Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem. In the 1970s, researchers began studying these algorithms from the point of view of worst-case analysis; see, for instance, Tarjan & Trojanowski (1977), an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of Cook (1971) and Karp (1972), researchers began finding mathematical justification for the perceived difficulty of the clique problem in the theory of NP-completeness and related intractability results. In the 1990s, a breakthrough series of papers beginning with Feige et al. (1991) and reported at the time in major newspapers, showed that it is not even possible to approximate the problem accurately and efficiently.
Read more about this topic: Clique Problem
Famous quotes containing the word history:
“We may pretend that we’re basically moral people who make mistakes, but the whole of history proves otherwise.”
—Terry Hands (b. 1941)
“As History stands, it is a sort of Chinese Play, without end and without lesson.”
—Henry Brooks Adams (1838–1918)
“... that there is no other way,
That the history of creation proceeds according to
Stringent laws, and that things
Do get done in this way, but never the things
We set out to accomplish and wanted so desperately
To see come into being.”
—John Ashbery (b. 1927)