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:
“Every member of the family of the future will be a producer of some kind and in some degree. The only one who will have the right of exemption will be the mother ...”
—Ruth C. D. Havens, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)
“Racism is an ism to which everyone in the world today is exposed; for or against, we must take sides. And the history of the future will differ according to the decision which we make.”
—Ruth Benedict (1887–1948)
“It’s not the sentiments of men which make history but their actions.”
—Norman Mailer (b. 1923)