期刊
COMPUTERS & OPERATIONS RESEARCH
卷 84, 期 -, 页码 1-15出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2017.02.017
关键词
Maximum clique problem; Branch-and-bound; Branching ordering; Incremental MaxSAT Reasoning
类别
资金
- National Natural Science Foundation of China [61472147, 61370184, 61272014]
- MeCS platform of the University of Picardie Jules Verne
- Ministerio de Educacion, Cultura y Deporte [PRX16/00215]
- Generalitat de Catalunya [AGAUR 2014-SGR-118]
- MINECO-FEDER project [RASO TIN2015-71799-C2-1-P]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据