An exact algorithm for the maximum clique problem with accelerated pruning
Panagote M. Pardalos, L. Gibbons, Donald W. Hearn · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We present an exact partial enumerative algorithm for the maximum clique problem. The pruning device used is derived from graph colorings. Pruning of the search tree is accomplished not only by the number of colors used to color a tree subproblem but also by using information gained in the process of coloring. This leads to increased pruning which translates into improved computational performance. Experimental results on test problems are presented.