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:
“The history of the genesis or the old mythology repeats itself in the experience of every child. He too is a demon or god thrown into a particular chaos, where he strives ever to lead things from disorder into order.”
—Ralph Waldo Emerson (1803–1882)
“The greatest honor history can bestow is that of peacemaker.”
—Richard M. Nixon (1913–1995)
“I believe that history might be, and ought to be, taught in a new fashion so as to make the meaning of it as a process of evolution intelligible to the young.”
—Thomas Henry Huxley (1825–95)