number of edges at most a constant times the number of vertices) and closed under the operation of taking subgraphs. Finding maximum cliques in arbitrary graphs It is possible to find the maximum clique, or the clique number, of an arbitrary n-vertex graph in time by using one of the algorithms described above to list all maximal cliques in the graph and returning the largest one. However, for this variant of the clique problem better worst-case time bounds are possible. The algorithm of solves this problem in time . It is a recursive backtracking scheme similar to that of the Bron–Kerbosch algorithm, but is able to eliminate some recursive calls when it can be shown that the cliques found within the call will be suboptimal. improved the time to , and improved it to time, at the expense of greater space usage. Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by which runs in time . There has also been extensive research on heuristic algorithms for solving maximum clique problems without worst-case runtime guarantees, based on methods including branch and bound, local search, greedy algorithms, and constraint programming. Non-standard computing methodologies that have been suggested for finding cliques include DNA computing and adiabatic quantum computation. The maximum clique problem was the subject of an implementation challenge sponsored by DIMACS in 1992–1993, and a collection of graphs used as benchmarks for the challenge, which is publicly available. Special classes of graphs Planar graphs, and other families of sparse graphs, have been discussed above: they have linearly many maximal cliques, of bounded size, that can be listed in linear time. In particular, for planar graphs, any clique can have at most four vertices, by Kuratowski's theorem. Perfect graphs are defined by the properties that their clique number equals their chromatic number, and that this equality holds also in each of their induced subgraphs. For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs.