On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
复制标题
最大团问题的分支定界算法中分支数最小化
DOI：
10.1016/j.cor.2017.02.017
复制
发表时间：
2017-08-01
影响因子：
4.6
通讯作者：
Manya, Felip
中科院分区：
文献类型：
--
作者：
Li, Chu-Min;Jiang, Hua;Manya, Felip
在图G中搜索最大团时，文献中的分支定界算法通常关注于在每个搜索树节点上生成的分支数量的最小化。我们称这种动态策略为没有任何约束的最小化，因为它在搜索过程中在G中引入了一个动态顶点排序。在本文中，我们引入了一种静态策略，该策略在搜索过程中必须保持G中的静态顶点顺序的约束下，最小化分支的数量。我们分析了这两种策略，并表明它们是互补的。基于这种互补性，我们提出了一种新的算法，称为MoMC，它将两种策略的优势结合到一个算法中。实验结果表明，MoMC算法总体上优于实现单一策略的算法。(C) 2017 Elsevier Ltd.版权所有。
When searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy. (C) 2017 Elsevier Ltd. All rights reserved.