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 条
  • [41] An asynchronous P system for solving the maximum clique problem with the Bron-Kerbosch algorithm
    Noguchi, Takuya
    Fujiwara, Akihiro
    2022 TENTH INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING WORKSHOPS, CANDARW, 2022, : 199 - 205
  • [42] 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)
  • [43] An Improved Chaotic Maximum Neural Network for Maximum Clique Problem
    Yang, Gang
    Tang, Zheng
    Yi, Junyan
    INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2007, 7 (02): : 1 - 7
  • [44] Subgraph extraction and metaheuristics for the maximum clique problem
    Duc-Cuong Dang
    Aziz Moukrim
    Journal of Heuristics, 2012, 18 : 767 - 794
  • [45] A SHRINKING CHAOTIC MAXIMUM NEURAL NETWORK FOR MAXIMUM CLIQUE PROBLEM
    Yi, Junyan
    Yang, Gang
    Gao, Shangce
    Tang, Zheng
    INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 2009, 5 (05): : 1213 - 1229
  • [46] 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)
  • [47] The Maximum Clique Problem in Multiple Interval Graphs
    Francis, Mathew C.
    Goncalves, Daniel
    Ochem, Pascal
    ALGORITHMICA, 2015, 71 (04) : 812 - 836
  • [48] Subgraph extraction and metaheuristics for the maximum clique problem
    Dang, Duc-Cuong
    Moukrim, Aziz
    JOURNAL OF HEURISTICS, 2012, 18 (05) : 767 - 794
  • [49] An optimization algorithm for maximum quasi-clique problem based on information feedback model
    Liu, Shuhong
    Zhou, Jincheng
    Wang, Dan
    Zhang, Zaijun
    Lei, Mingjie
    PEERJ COMPUTER SCIENCE, 2024, 10
  • [50] An effective local search for the maximum clique problem
    Katayama, K
    Hamamoto, A
    Narihisa, H
    INFORMATION PROCESSING LETTERS, 2005, 95 (05) : 503 - 511
12345