Reactive Local Search for the Maximum Clique Problem1

被引:0
|
作者
R. Battiti
M. Protasi
机构
[1] Dipartimento di Matematica,
[2] Universitá of Trento,undefined
[3] Via Sommarive 14,undefined
[4] 38050 Povo (Trento),undefined
[5] Italy. battiti@ science.unitn.it.,undefined
[6] Dipartimento di Matematica,undefined
[7] Universitá di Roma ``Tor Vergata'',undefined
[8] Roma,undefined
[9] Italy. Marco died on February 1,undefined
[10] 1998.,undefined
来源
Algorithmica | 2001年 / 29卷
关键词
Key words. Maximum-clique problem, Heuristic algorithms, Tabu search, Reactive search.;
D O I
暂无
中图分类号
学科分类号
摘要
A new Reactive Local Search (\RLS ) algorithm is proposed for the solution of the Maximum-Clique problem. \RLS is based on local search complemented by a feedback (history-sensitive) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O(max {n,m}) where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs.
引用
收藏
页码:610 / 637
页数:27
相关论文
共 50 条
  • [21] A Scatter Search algorithm for the Maximum Clique Problem
    Cavique, L
    Rego, C
    Themido, I
    ESSAYS AND SURVEYS IN METAHEURISTICS, 2002, 15 : 227 - 244
  • [22] Parallel Bounded Search for the Maximum Clique Problem
    Hua Jiang
    Ke Bai
    Hai-Jiao Liu
    Chu-Min Li
    Felip Manyà
    Zhang-Hua Fu
    Journal of Computer Science and Technology, 2023, 38 : 1187 - 1202
  • [23] SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem
    Wang, Yiyuan
    Cai, Shaowei
    Chen, Jiejiang
    Yin, Minghao
    ARTIFICIAL INTELLIGENCE, 2020, 280 (280)
  • [24] A local search algorithm with hybrid strategies for the maximum weighted quasi-clique problem
    Zhou, Jincheng
    Liu, Shuhong
    Gao, Jian
    ELECTRONICS LETTERS, 2023, 59 (01)
  • [25] An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
    Chu, Yi
    Liu, Boxiao
    Cai, Shaowei
    Luo, Chuan
    You, Haihang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 39 (04) : 933 - 954
  • [26] An Iterated Local Search ILS-CHC for the Maximum Vertex-Weighted Clique Problem
    Tayachi, D.
    Zaddem, N.
    2018 5TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), 2018, : 555 - 562
  • [27] A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
    Nogueira, Bruno
    Pinheiro, Rian G. S.
    COMPUTERS & OPERATIONS RESEARCH, 2018, 90 : 232 - 248
  • [28] A novel parallel local search algorithm for the maximum vertex weight clique problem in large graphs
    Sevinc, Ender
    Dokeroglu, Tansel
    SOFT COMPUTING, 2020, 24 (05) : 3551 - 3567
  • [29] A novel parallel local search algorithm for the maximum vertex weight clique problem in large graphs
    Ender Sevinc
    Tansel Dokeroglu
    Soft Computing, 2020, 24 : 3551 - 3567
  • [30] An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
    Yi Chu
    Boxiao Liu
    Shaowei Cai
    Chuan Luo
    Haihang You
    Journal of Combinatorial Optimization, 2020, 39 : 933 - 954