An effective local search for the maximum clique problem
An effective local search for the maximum clique problem
复制标题
DOI：
10.1016/j.ipl.2005.05.010
复制
发表时间：
2005-09-15
影响因子：
0.5
通讯作者：
Narihisa, H
中科院分区：
文献类型：
--
作者：
Katayama, K;Hamamoto, A;Narihisa, H
我们提出了一种基于可变深度搜索的算法，称为k-opt局部搜索（KLS），最大团问题。KLS有效地探索了k-opt邻域，该邻域被定义为可以通过在可行搜索空间中自适应地改变的几个添加和删除移动的序列来获得的邻域的集合。DIMACS基准图上的计算结果表明，KLS是能够找到相当满意的集团与合理的运行时间相比，那些国家的最先进的metacerstics。(c)2005 Elsevier B. V.保留所有权利。
We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics. (c) 2005 Elsevier B.V. All rights reserved.