Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound
Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound
复制标题
DOI：
10.1016/j.dam.2017.01.026
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Satoshi Shimizu;Kazuaki Yamaguchi;Toshiki Saitoh;S. Masuda
中科院分区：
文献类型：
--
作者：
Satoshi Shimizu;Kazuaki Yamaguchi;Toshiki Saitoh;S. Masuda
针对最大权团问题，提出了一种新的分支定界算法。该算法由两个阶段组成：预计算阶段和分支定界阶段。在预计算阶段，计算许多小子图中最大权重团的权重并将其存储在最优表中。在分支定界阶段，每个问题被分成更小的子问题，并使用最优表修剪不必要的子问题。我们使用所提出的算法和五种现有算法针对多种类型的图进行了实验。结果表明，只有所提出的算法才能获得所有图的精确解，并且对于几乎所有图，它的执行速度比其他算法快得多。
A new branch-and-bound algorithm for the maximum weight clique problem is proposed. The proposed algorithm consists of two phases, aprecomputation phaseand abranch-and-bound phase. In the precomputation phase, the weights of maximum weight cliques in many small subgraphs are calculated and stored inoptimal tables. In the branch-and-bound phase, each problem is divided into smaller subproblems, and unnecessary subproblems are pruned using the optimal tables. We performed experiments with the proposed algorithm and five existing algorithms for several types of graphs. The results indicate that only the proposed algorithm can obtain exact solutions for all graphs and that it performs much faster than other algorithms for nearly all graphs.