An effective local search for the maximum clique problem |
| |
Authors: | Kengo Katayama Akihiro Hamamoto Hiroyuki Narihisa |
| |
Affiliation: | Department of Information and Computer Engineering, Okayama University of Science, 1-1 Ridai-cho, Okayama 700-0005, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Graph algorithms Combinatorial optimization Variable depth search Neighborhood Maximum clique problem |
本文献已被 ScienceDirect 等数据库收录! |