A simple and efficient branch and bound algorithm for finding a maximum clique with experimental evaluations
Etsuji Tomita, Ken'ichi Imamatsu, Yasuhiro Kohata, Mitsuo Wakatsuki · Systems and Computers in Japan · 1997
In this paper a simple and efficient branch and bound algorithm to extract a maximum clique from an undirected graph is proposed. In this method the crucial point for improving the efficiency of the algorithm is how to make the search space small using a tighter bound. However, the processing time to implement that bound must be kept small. Thus, in this paper a very simple and clever sequential approximate coloring-arranging method is developed considering trade-offs between these two factors. Using this, an upper bound on the maximum clique size at each search step is computed and branches are pruned based on this bound. The total computation time has been successfully reduced using this method. It has been verified either by computational experiments or by comparing published experimental results that this algorithm is faster than other major algorithms on a wide range of random graphs with 600 or less vertices and on a number of random graphs with 1,000 vertices. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(5): 60–67, 1997