A New Genetic Algorithm for the Maximum Clique Problem

被引：0
作者：
Evin, Gozde Kizilates [1 ]
机构：
[1] Ege Univ, Fac Sci, Dept Math, Izmir, Turkey
来源：
ARTIFICIAL INTELLIGENCE AND APPLIED MATHEMATICS IN ENGINEERING PROBLEMS | 2020年 / 43卷
关键词：
Maximum clique problem; Graph theory; Optimization problems; Heuristic algorithms; Hybrid genetic algorithms; BOUND ALGORITHM; SEARCH;
D O I：
10.1007/978-3-030-36178-5_66
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The Maximum Clique Problem is widely studied optimization problem and plays an essential part in computer science. In the literature, therefore, there are many exact and heuristic approaches and new strategies are continuously being proposed. In this paper, the maximum clique problem is studied, and a new hybrid genetic algorithm is proposed for finding the maximum clique in a graph. The proposed algorithm is tested on the DIMACS and BHOSLIB benchmark instances. The computational results are compared with similar literature researches. The results prove the effectiveness of proposed algorithm.
引用
收藏
页码：766 / 774
页数：9
相关论文
共 50 条
  • [31] Numerical experiments with LP formulations of the maximum clique problem
    Kardos, Dora
    Patassy, Patrik
    Szabo, Sandor
    Zavalnij, Bogdan
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2022, 30 (04) : 1353 - 1367
  • [32] An opposition-based memetic algorithm for the maximum quasi-clique problem
    Zhou, Qing
    Benlic, Una
    Wu, Qinghua
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 286 (01) : 63 - 83
  • [33] A chaotic maximum neural network for maximum clique problem
    Wang, JH
    Tang, Z
    Wang, RL
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (07): : 1953 - 1961
  • [34] Algorithm for Uniform Test Assembly Using a Maximum Clique Problem and Integer Programming
    Ishii, Takatoshi
    Ueno, Maomi
    ARTIFICIAL INTELLIGENCE IN EDUCATION, AIED 2017, 2017, 10331 : 102 - 112
  • [35] An algorithm for finding a maximum clique in a graph
    Wood, DR
    OPERATIONS RESEARCH LETTERS, 1997, 21 (05) : 211 - 217
  • [36] Novel Algorithm to Find Maximum Clique
    Chhatani, Jyoti
    Chaudhary, Juhi
    2019 FIFTH INTERNATIONAL CONFERENCE ON IMAGE INFORMATION PROCESSING (ICIIP 2019), 2019, : 286 - 291
  • [37] A new exact maximum clique algorithm for large and massive sparse graphs
    San Segundo, Pablo
    Lopez, Alvaro
    Pardalos, Panos M.
    COMPUTERS & OPERATIONS RESEARCH, 2016, 66 : 81 - 94
  • [38] Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem
    Troiani, Alessio
    MATHEMATICS, 2024, 12 (18)
  • [39] Sticker model for maximum clique problem and maximum independent set
    Fan Y.-K.
    Qiang X.-L.
    Xu J.
    Jisuanji Xuebao/Chinese Journal of Computers, 2010, 33 (02): : 305 - 310
  • [40] Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements
    Maslov, Evgeny
    Batsyn, Mikhail
    Pardalos, Panos M.
    MODELS, ALGORITHMS, AND TECHNOLOGIES FOR NETWORK ANALYSIS, 2013, 59 : 93 - 99
12345