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:
“I feel as tall as you.”
—Ellis Meredith, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 14, by Susan B. Anthony and Ida Husted Harper (1902)
“If you look at the 150 years of modern China’s history since the Opium Wars, then you can’t avoid the conclusion that the last 15 years are the best 15 years in China’s modern history.”
—J. Stapleton Roy (b. 1935)
“To care for the quarrels of the past, to identify oneself passionately with a cause that became, politically speaking, a losing cause with the birth of the modern world, is to experience a kind of straining against reality, a rebellious nonconformity that, again, is rare in America, where children are instructed in the virtues of the system they live under, as though history had achieved a happy ending in American civics.”
—Mary McCarthy (1912–1989)