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 条
  • [1] Reactive local search for the maximum clique problem
    Battiti, R
    Protasi, M
    ALGORITHMICA, 2001, 29 (04) : 610 - 637
  • [2] Dynamic local search for the maximum clique problem
    Pullan, W
    Hoos, HH
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2006, 25 (159-185): : 159 - 185
  • [4] Cooperating local search for the maximum clique problem
    Pullan, Wayne
    Mascia, Franco
    Brunato, Mauro
    JOURNAL OF HEURISTICS, 2011, 17 (02) : 181 - 199
  • [5] An effective local search for the maximum clique problem
    Katayama, K
    Hamamoto, A
    Narihisa, H
    INFORMATION PROCESSING LETTERS, 2005, 95 (05) : 503 - 511
  • [6] Cooperating local search for the maximum clique problem
    Wayne Pullan
    Franco Mascia
    Mauro Brunato
    Journal of Heuristics, 2011, 17 : 181 - 199
  • [7] Phased local search for the maximum clique problem
    Wayne Pullan
    Journal of Combinatorial Optimization, 2006, 12 : 303 - 323
  • [8] An Efficient Local Search for the Maximum Edge Weighted Clique Problem
    Li, Ruizhi
    Wu, Xiaoli
    Liu, Huan
    Wu, Jun
    Yin, Minghao
    IEEE ACCESS, 2018, 6 : 10743 - 10753
  • [9] Genetic, iterated and multistart local search for the maximum clique problem
    Marchiori, E
    APPLICATIONS OF EVOLUTIONARY COMPUTING, PROCEEDINGS, 2002, 2279 : 112 - 121
  • [10] An Efficient Local Search for the Maximum Clique Problem on Massive Graphs
    Kanahara, Kazuho
    Oda, Tetsuya
    Kulla, Elis
    Uejima, Akira
    Katayama, Kengo
    ADVANCES IN INTERNET, DATA & WEB TECHNOLOGIES (EIDWT-2022), 2022, 118 : 201 - 211