next up previous
Next: Coloring Up: Solution Approaches Previous: Solution Approaches


There is a vast literature covering algorithms for this problem. An extensive survey is [76], available by anonymous FTP from DIMACS.

A very common approach to the problem of finding (truly) maximum clique is to use some variant on implicit enumeration. Some examples of use of this technique are Bron and Kerbosch [20], Akkoyunlu [2], Gerhards and Lindenberg [42], Loukakis and Tsouros [65], and Carraghan and Pardalos [22].

Approaches based on branch and bound include Babel [7] Balas and Yu [10], and Balas and Xue [9], which use coloring to obtain the required bounds, and Pardalos and Rodgers [75], which uses quadratic programming to obtain its bounds.

Polyedral approaches have been suggested by Nemhauser and Trotter [72] and Balas and Samuelsson [8].

Tarjan and Trojanowski [79] develop a recursive routine which has a worst case bound of .

There has been much theoretical work on the application of approximation algorithms to random graphs (where typically a random graph is one chosen uniformly at random from the set of all labeled graphs). Bollobás and Erdös [16] and Bollobás and Thomason [17] have very strong bounds on the size of the largest clique. Pittel [78] has analyzed a number of heuristics for such graphs, and found none that will find the largest clique in this model. Jerrum [50] has extended this work to include heuristics based on simulated annealing.

Other heuristic approaches that have been considered for clique include the ``GRASP'' technique of Feo, Resende, and Smith [36] and the use of interior point methods by Karmarkar, Ramakrishnan, and Resende [55].

Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994