A branch and bound algorithm for the maximum clique problem
A branch and bound algorithm for the maximum clique problem
复制标题
DOI：
10.1016/0305-0548(92)90067-f
复制
发表时间：
1992-07
期刊：
影响因子：
--
通讯作者：
P. Pardalos;G. P. Rodgers
中科院分区：
文献类型：
--
作者：
P. Pardalos;G. P. Rodgers
提出了一种基于无约束二次0 - 1规划求解最大团问题的方法。给出了无约束二次0 - 1规划的一个分支定界算法，该算法采用动态选择变量的方法来确定分支树的排序。动态变量选择等价于最大团问题的类似分支定界算法中的顶点选择。在本文中，我们比较了两种不同的规则选择一个顶点。第一个规则选择对应于具有高连通性的顶点的变量（贪婪方法），第二个规则选择对应于具有低连通性的顶点的变量（非贪婪方法）。我们证明了第一个规则发现一个最大的集团更快，但它需要更长的时间来验证最优性。一个有效的可向量化的实现IBM 3090上的计算结果提供了随机生成的图形与多达1000个顶点和150,000条边。
A method to solve the maximum clique problem based on an unconstrained quadratic zero-one programming formulation is presented. A branch and bound algorithm for unconstrained quadratic zero-one programming is given that uses a technique to dynamically select variables for the ordering of the branching tree. Dynamic variable selection is equivalent to vertex selection in a similar branch and bound algorithm for the maximum clique problem. In this paper we compare two different rules for selecting a vertex. The first rule selects a variable corresponding to a vertex with high connectivity (a greedy approach) and the second rule selects a variable corresponding to a vertex with low connectivity (a nongreedy approach). We demonstrate that the first rule discovers a maximum clique sooner but it takes significantly longer to verify optimality. Computational results for an efficient vectorizable implementation on an IBM 3090 are provided for randomly generated graphs with up to 1000 vertices and 150,000 edges.