基于Q0-1规划模型用分枝定界法求解最大团问题

The Branch and Bound Algorithms for Maximum Clique Problem Based on Q0-1 Programming

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型(简称Q0-1规划模型)寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。

To search the maximum clique of a graph is a classical NP-hard in many years, in this paper, we proved that maximum clique problem of a graph can be equivalent to a kind of special Q0-1 programming problem. Then with the help of branch and bound algorithms, we found the method of searching the maximum clique of a graph, and presented an example to prove the effectiveness of the algorithm.