Study On Maximum Clique Problem And Its Branch And Bound Alecrithms

The theory results and heuristics of the maximum clique problem are described and the branch and bound algorithms are discussed in detail in this paper. Based on these existing algorithms, We present a new branch and bound algorithm for the maximum weight clique problem. The algorithm applies a simple clique finding and weighted coloring to determine lower and upper bounds, and actives exactly one new search tree node at each branching stage which using the information obtained in the weighted coloring to choose a branching vertex, and uses backtracking method to obtain optimum solution. The algorithm provides the possibility of reducing the size of the search tree and running time.