AN ALGORITHM FOR SOLVING GRAPH COLORING PROBLEMS BASED ON AN IMPROVED ANT COLONY OPTIMIZATION

被引：0
作者：
Zhou, Supei [1 ]
机构：
[1] Zhejiang Sci Tech Univ, Sch Sci, Hangzhou 310018, Zhejiang, Peoples R China
来源：
UNIVERSITY POLITEHNICA OF BUCHAREST SCIENTIFIC BULLETIN SERIES C-ELECTRICAL ENGINEERING AND COMPUTER SCIENCE | 2023年 / 85卷 / 02期
关键词：
graph coloring problem; ant colony optimization; greedy algorithm; social networks; link prediction;
D O I：
暂无
中图分类号：
TM [电工技术]; TN [电子技术、通信技术];
学科分类号：
0808 ; 0809 ;
摘要：
The Graph Coloring Problem (GCP) is a significant research area in graph theory, and new breakthroughs are constantly being made, while the ant colony optimization shows its outstanding ability to solve path planning problems. In this research, the ant colony optimization method is made full use of to improve it using one kind of greedy algorithm, and the effectiveness of this proposed solution algorithm for the coloring problem in a realistic directed and undirected network environment is validated. It is demonstrated that the proposed GAC-GC graph coloring solution method has better efficiency and accuracy than the classical algorithm for coloring problems. In future research, further improvements can be made from various perspectives, such as application scenarios, integrated application of algorithmic data pre-processing, and hybrid algorithm improvement.
引用
收藏
页码：209 / 220
页数：12
相关论文
共 50 条
  • [41] Mobile Robot Path Planning Based on Improved Ant Colony Optimization Algorithm
    Zhao Juanping
    Gao Xianwen
    Fu Xiuhui
    [J]. 2011 30TH CHINESE CONTROL CONFERENCE (CCC), 2011, : 4102 - 4104
  • [42] Improved CCN Routing Based on the Combination of Genetic Algorithm and Ant Colony Optimization
    Huang, Pei
    Chen, Jianya
    [J]. 2013 3RD INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT), 2013, : 846 - 849
  • [43] An improved ant colony optimization based algorithm for the capacitated arc routing problem
    Santos, Luis
    Coutinho-Rodrigues, Joao
    Current, John R.
    [J]. TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2010, 44 (02) : 246 - 266
  • [44] Discrete Particle Swarm Optimization Algorithm for Solving Graph Coloring Problem
    Zhang, Kai
    Zhu, Wanying
    Liu, Jun
    He, Juanjuan
    [J]. BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 : 643 - 652
  • [45] Hybridizing ant colony optimization with firefly algorithm for unconstrained optimization problems
    Rizk-Allah, R. M.
    Zaki, Elsayed M.
    El-Sawy, Ahmed Ahmed
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2013, 224 : 473 - 483
  • [46] Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems
    Hung, Kuo-Sheng
    Su, Shun-Feng
    Lee, Zne-Jung
    [J]. JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS, 2007, 11 (04) : 433 - 442
  • [47] Ant Colony Optimization with Negative Feedback for Solving Constraint Satisfaction Problems
    Masukane, Takuya
    Mizuno, Kazunori
    Shinohara, Hiroto
    [J]. 2018 CONFERENCE ON TECHNOLOGIES AND APPLICATIONS OF ARTIFICIAL INTELLIGENCE (TAAI), 2018, : 156 - 159
  • [48] Improved clonal selection algorithm combined with ant colony optimization
    Gao, Shangce
    Wang, Wei
    Dai, Hongwei
    Li, Fangjia
    Tang, Zheng
    [J]. IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2008, E91D (06) : 1813 - 1823
  • [49] Improved Ant Colony Optimization Algorithm for UAV Path Planning
    Cui, Can
    Wang, Nan
    Chen, Jing
    [J]. 2014 5TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE (ICSESS), 2014, : 291 - 295
  • [50] Solving the Capacitated Location Routing Problem by Ant Colony Optimization Algorithm
    Ting, Ching-Jung
    Chen, Chia-Ho
    [J]. PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON OPERATIONS AND SUPPLY CHAIN MANAGEMENT, 2008, : 227 - 234
12345