Computer Science
In computer science, the clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete, one of Karp's 21 NP-complete problems (Karp 1972). It is also fixed-parameter intractable, and hard to approximate. Nevertheless, many algorithms for computing cliques have been developed, either running in exponential time (such as the Bron–Kerbosch algorithm) or specialized to graph families such as planar graphs or perfect graphs for which the problem can be solved in polynomial time.
Read more about this topic: Clique (graph Theory)
Famous quotes containing the words computer and/or science:
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)
“We know only a single science, the science of history. One can look at history from two sides and divide it into the history of nature and the history of men. However, the two sides are not to be divided off; as long as men exist the history of nature and the history of men are mutually conditioned.”
—Karl Marx (1818–1883)