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:
“All history attests that man has subjected woman to his will, used her as a means to promote his selfish gratification, to minister to his sensual pleasures, to be instrumental in promoting his comfort; but never has he desired to elevate her to that rank she was created to fill. He has done all he could to debase and enslave her mind; and now he looks triumphantly on the ruin he has wrought, and say, the being he has thus deeply injured is his inferior.”
—Sarah M. Grimke (1792–1873)
“The whole history of civilisation is strewn with creeds and institutions which were invaluable at first, and deadly afterwards.”
—Walter Bagehot (1826–1877)
“One classic American landscape haunts all of American literature. It is a picture of Eden, perceived at the instant of history when corruption has just begun to set in. The serpent has shown his scaly head in the undergrowth. The apple gleams on the tree. The old drama of the Fall is ready to start all over again.”
—Jonathan Raban (b. 1942)