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:
“The archetype of all humans, their ideal image, is the computer, once it has liberated itself from its creator, man. The computer is the essence of the human being. In the computer, man reaches his completion.”
—Friedrich Dürrenmatt (1921–1990)
“The great pagan world of which Egypt and Greece were the last living terms ... once had a vast and perhaps perfect science of its own, a science in terms of life. In our era this science crumbled into magic and charlatanry. But even wisdom crumbles.”
—D.H. (David Herbert)