Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (18): 66-77.DOI: 10.3778/j.issn.1002-8331.2403-0434
• Research Hotspots and Reviews • Previous Articles Next Articles
SONG Jiahuan, WANG Xiaofeng, HU Simin, JIA Jingwei, YAN Dong
Online:
2024-09-15
Published:
2024-09-13
宋家欢,王晓峰,胡思敏,贾璟伟,颜冬
SONG Jiahuan, WANG Xiaofeng, HU Simin, JIA Jingwei, YAN Dong. Algorithmic Research Overview on Graph Coloring Problems[J]. Computer Engineering and Applications, 2024, 60(18): 66-77.
宋家欢, 王晓峰, 胡思敏, 贾璟伟, 颜冬. 图着色问题的算法研究综述[J]. 计算机工程与应用, 2024, 60(18): 66-77.
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2403-0434
[1] LIU S C. A renewal approach to prove the four color theorem unplugged, part III: diamond routes, canal lines and ??-adjustments[J]. arXiv:2309.09998, 2023. [2] KAINZ W. Cartography and the others-aspects of a complicated relationship[J]. Geo-Spatial Information Science, 2020, 23(1): 52-60. [3] OUSSEIN E H, GAD A G, WAZERY Y M, et al. Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends[J]. Swarm and Evolutionary Computation, 2021, 62: 100841. [4] IBRAHIM I M. Task scheduling algorithms in cloud computing: a review[J]. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 2021, 12(4): 1041-1053. [5] NABI S, AHMAD M, IBRAHIM M, et al. AdPSO: adaptive PSO-based task scheduling approach for cloud computing[J]. Sensors, 2022, 22(3): 920. [6] WANG H, WANG K, YANG J, et al. GCN-RL circuit designer: transferable transistor sizing with graph neural networks and reinforcement learning[C]//2020 57th ACM/IEEE Design Automation Conference (DAC), 2020: 1-6. [7] PANIGRAHI P, SAHITHYA V, KARFA C, et al. Secure register allocation for trusted code generation[J]. IEEE Embedded Systems Letters, 2022, 14(3): 127-130. [8] ZHANG Y, CHEN W, LING H, et al. Image gans meet differentiable rendering for inverse graphics and interpretable 3D neural rendering[J]. arXiv:2010.09125, 2020. [9] KATOCH S, CHAUHAN S S, KUMAR V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80: 8091-8126. [10] SQUIRES M, TAO X E,ALNGOVAN S, et al. A novel genetic algorithm based system for the scheduling of medical treatments[J]. Expert Systems with Applications, 2022, 195: 116464. [11] SDENG W, ZHANG X, ZHOU Y, et al. An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems[J]. Information Sciences, 2022, 585: 441-453. [12] SHAMI T M, EL-SALEH A A, ALAWAITTIl M, et al. Particle swarm optimization: a comprehensive survey[J]. IEEE Access, 2022, 10: 10031-10061. [13] GAD A G. Particle swarm optimization algorithm and its applications: a systematic review[J]. Archives of Computational Methods in Engineering, 2022, 29(5): 2531-2561. [14] ROKBANI N, KUMAR R, ABRAHAM A, et al. Bi-heuristic ant colony optimization-based approaches for traveling salesman problem[J]. Soft Computing, 2021, 25: 3775-3794. [15] WANG G G, GAO D, PEDRYCZ W. Solving multiobjective fuzzy job-shop scheduling problem by a hybrid adaptive differential evolution algorithm[J]. IEEE Transactions on Industrial Informatics, 2022, 18(12): 8519-8528. [16] ZHANG D, GAO Z, LIN Z. An online control approach for forging machine using reinforcement learning and taboo search[J]. IEEE Access, 2020, 8: 158666-158678. [17] WANG Y, QIAN M. Vegetable price and supply forecast based on the taboo search algorithm[J]. Highlights in Science, Engineering and Technology, 2024, 82: 37-42. [18] CAO J, ZHANG F, LU Y, et al. Modeling optimization of distributed prefabricated manufacturing system based on iterative taboo search algorithm[C]//2023 3rd International Symposium on Artificial Intelligence and Intelligent Manufacturing (AIIM), 2023: 111-115. [19] KUMAR S, TRIPATHI D R R. To study the financial performance of top five privatized banks in India with special reference to (HDFC, AXIS, ICICI, KMB, IndusInd Bank)[J]. Journal of Contemporary Issues in Business and Government, 2021, 27(6). [20] ZHANG K, KOREPIN V E. Depth optimization of quantum search algorithms beyond Grover’s algorithm[J]. Physical Review A, 2020, 101(3): 032346. [21] DU Y, HUANG T, YOU S, et al. Quantum circuit architecture search for variational quantum algorithms[J]. npj Quantum Information, 2022, 8(1): 62. [22] BHARTI K, CERVERA-LIERTA A, KYAW T H, et al. Noisy intermediate-scale quantum algorithms[J]. Reviews of Modern Physics, 2022, 94(1): 015004. [23] CLIFTON J, LABER E. Q-learning: theory and applications[J]. Annual Review of Statistics and Its Application, 2020, 7: 279-301. [24] YANG K, YANG L, DU S. Q-learning with logarithmic regret[C]//International Conference on Artificial Intelligence and Statistics, 2021: 1576-1584. [25] GAO Z, GAO Y, HU Y, et al. Application of deep q-network in portfolio management[C]//2020 5th IEEE International Conference on Big Data Analytics (ICBDA), 2020: 268-275. [26] UCHIDA Y, YAJIMA K, HARAGUCHI K. Recycling solutions for vertex coloring heuristics[J]. Journal of the Operations Research Society of Japan, 2021, 64(3): 184-202. [27] VERMA G,ARORA J,SETHI R, et al. Handmade cloning:recent advances,potential and pitfalls[J].Journal of Animal Science and Biotechnology, 2015, 6(4): 378-387. [28] CORDEAU J F, FURINI F, LJUBIC I. Benders decomposition for very large scale partial set covering and maximal covering location problems[J]. European Journal of Operational Research, 2019, 275(3): 882-896. [29] RAUCHECKER G, SCHRYEN G. An exact branch-and-price algorithm for scheduling rescue units during disaster response[J]. European Journal of Operational Research, 2019, 272(1): 352-363. [30] GOYAL J M, MAYNE N, SING D K, et al. A library of ATMO forward model transmission spectra for hot Jupiter exoplanets[J]. Monthly Notices of the Royal Astronomical Society, 2018, 474(4): 5158-5185. [31] SELSAM D, LAMM M, BUNZ B, et al. Learning a SAT solver from single-bit supervision[J]. arXiv:1802.03685, 2018. [32] LOUKAS A. What graph neural networks cannot learn: depth vs width[J]. arXiv:1907.03199, 2019. [33] ZHAO R, WANG Y, LIU C, et al. Discrete selfish herd optimizer for solving graph coloring problem[J]. Applied Intelligence, 2020, 50: 1633-1656. [34] DHULIPALA L, BLELLOCH G E, SHUN J. Theoretically efficient parallel graph algorithms can be fast and scalable[J]. ACM Transactions on Parallel Computing (TOPC), 2021, 8(1): 1-70. [35] CHRISTOFIDES N. Worst-case analysis of a new heuristic for the travelling salesman problem[C]//Operations Research Forum. Cham: Springer International Publishing, 2022. [36] BRIGHEN A, SLIMANI H, REZGUI A, et al. A new distributed graph coloring algorithm for large graphs[J]. Cluster Computing, 2023, 27(1): 875-891. [37] XU C, MA J, TAO H. Batch process control based on reinforcement learning with segmented prioritized experience replay[J]. Measurement Science and Technology, 2024, 35(5): 056202. [38] HAN J X, MA M Y, WANG K. Product modeling design based on genetic algorithm and BP neural network[J]. Neural Computing and Applications, 2021, 33: 4111-4117. [39] BESTA M, CARIGIET A, JANDA K, et al. High-performance parallel graph coloring with strong guarantees on work, depth, and quality[C]//SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, 2020: 1-17. [40] SINGLA M K, NIJHAWAN P, OBEROI A S. Parameter estimation of three diode solar PV cell using chaotic dragonfly algorithm[J]. Soft Computing, 2022, 26(21): 11567-11598. [41] PIKIES T, TUROWSKI K, KUBALE M. Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms[J]. Artificial Intelligence, 2022, 309: 103711. [42] BINUCCI C, DI-BATTISTA G, DIDIMO W, et al. Nonplanar graph drawings with k vertices per face[C]//International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer Nature Switzerland, 2023: 86-100. [43] ALSMADI M K. Content-based image retrieval using color, shape and texture descriptors and features[J]. Arabian Journal for Science and Engineering, 2020, 45(4): 3317-3330. [44] MARAPPAN R, SETHUMADHAVAN G. Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization[J]. Arabian Journal for Science and Engineering, 2021,47: 9695-9712. [45] BASAK S, SAMANTA K K. Thermal behaviour and the cone calorimetric analysis of the jute fabric treated in different pH condition[J].Journal of Thermal Analysis and Calorimetry, 2019, 135(6): 3095-3105. [46] PRASTYO P H, HIDAYAT R, ARDIYANTO I. Enhancing sentiment classification performance using hybrid query expansion ranking and binary particle swarm optimization with adaptive inertia weights[J]. ICT Express, 2022, 8(2): 189-197. [47] ZHANG X P, ZHANG Y P, FENG S S. An ant colony genetic algorithm for solvinggraph coloring problems[J]. Computer Applications and Software, 2014, 31(11): 207-209. [48] SHIMIZU K, MORI R. Exponential-time quantum algorithms for graph coloring problems[J]. Algorithmica, 2022, 84(12): 3603-3621. [49] GUO P, GUO B. NERS_HEAD: a new hybrid evolutionary algorithm for solving graph coloring problem[J]. Soft Computing, 2023, 27(17): 12117-12131. [50] CIARELLA S, TRINQUIER J, WEIGT M, et al. Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems[J]. Machine Learning: Science and Technology, 2023, 4(1): 010501. [51] 马艳萍, 吴晓军, 杨明成. 解决图着色问题的一种新禁忌搜索算法[J]. 计算机应用与软件, 2012, 29(2): 279-281. MA Y P, WU X J, YANG M C. A new tabu search algorithm for graph colouring[J]. Computer Applications and Software, 2012, 29(2): 279-281. [52] 汪建昌. 基于禁忌搜索算法解决图着色问题[D]. 昆明: 云南大学, 2022. WANG J C. Solving graph coloring problem based on tabu search algorithm [D]. Kunming: Yunnan University, 2022. [53] 汪建昌, 王硕, 李壮, 等. 图着色问题禁忌搜索改进算法[J]. 计算机科学, 2022, 49(S2): 94-98. WANG J C, WANG S, LI Z, et al. Improved algorithm for tabu search of graph coloring problems[J]. Computer Science, 2022, 49(S2): 94-98. [54] 刘晓楠, 刘正煜, 谢浩山, 等. 基于Grover算法的图着色问题求解[J]. 计算机科学, 2023, 50(6): 351-357. LIU X N, LIU Z Y, XIE H S, et al. Solving graph coloring problem based on Grover algorithm[J]. Computer Science, 2023, 50(6): 351-357. [55] JAYAGOPAL P, PURUSHPTHAMAN J K, MOHAN P, et al. A modified generative adversarial networks with Yolov5 for automated forest health diagnosis from aerial imagery and tabu search algorithm[J]. Scientific Reports, 2024, 14(1): 4814. [56] NOGUEIRA B, TAVARES E, MACIEL P. Iterated local search with tabu search for the weighted vertex coloring problem[J]. Computers & Operations Research, 2021, 125: 105087. [57] PERVEEN K, DEBNATH S, PANDEY B, et al. Deep learning-based multiscale CNN-based U network model for leaf disease diagnosis and segmentation of lesions in tomato[J]. Physiological and Molecular Plant Pathology, 2023, 128: 102148. [58] TAN Z, LI K. Differential evolution with mixed mutation strategy based on deep reinforcement learning[J]. Applied Soft Computing, 2021, 111: 107678. [59] GIRMA R, FURST C, MOGES A. Land use land cover change modeling by integrating artificial neural network with cellular Automata-Markov chain model in Gidabo river basin, main Ethiopian rift[J]. Environmental Challenges, 2022, 6: 100419. [60] DEY N N, Al R A, KAFY A A, et al. Geospatial modelling of changes in land use/land cover dynamics using multi-layer perceptron Markov chain model in Rajshahi City, Bangladesh[J]. Environmental Challenges, 2021, 4: 100148. [61] BAR A, SHAPIRA B, ROKACH L. Context aware Markov chains models[J]. Knowledge-Based Systems, 2023, 282: 111083. [62] DEGUALE D A, YU L, SINISHAW M L, et al. Enhancing stability and performance in mobile robot path planning with PMR-dueling DQN algorithm[J]. Sensors, 2024, 24(5): 1523. [63] CHEN W, QIU X, CAI T, et al. Deep reinforcement learning for Internet of things: a comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2021, 23(3): 1659-1692. [64] 吕恒. 解决图着色问题的膜进化算法研究[D]. 重庆: 重庆大学, 2022. LV H. Research on membrane evolutionary algorithm for graph coloring problem[D]. Chongqing: Chongqing University, 2022. |
[1] | WANG Junxia, WANG Xiaofeng, PENG Qingyuan, HUA Yingying, SONG Jiahuan. Review of Algorithmic Research on Steiner Tree Optimization Problems [J]. Computer Engineering and Applications, 2024, 60(9): 19-29. |
[2] | CHEN Lifang, CAO Kexin, ZHANG Sipeng, BAI Haoran, HAN Yang, DAI Qi. Recent Progress of Swarm Intelligent Optimization Algorithms [J]. Computer Engineering and Applications, 2024, 60(19): 46-67. |
[3] | PU Linfa, YANG Yajun, WANG Xin. Constrained Multi-Start Path Planning Algorithm on Large-Scale Graphs [J]. Computer Engineering and Applications, 2023, 59(6): 283-290. |
[4] | JIA Heming, CHEN Lizhen, LI Shanglong, LIU Qingxin, WU Di, LU Chenghao. Optimization Algorithm of Elite Pool Dwarf Mongoose Based on Lens Imaging Reverse Learning [J]. Computer Engineering and Applications, 2023, 59(24): 131-139. |
[5] | PANG Qingle, ZHENG Yang, MA Zhaoxing, HE Chenbin. Application of IGWO-IP&O Algorithm in PV Energy Storage MPPT Control System [J]. Computer Engineering and Applications, 2023, 59(20): 306-317. |
[6] | LU Shichang, SHAO Xulun, LI Dan. Research on Truck-Drone Coordinated Disaster Relief Supplies Obstacle Avoidance Distribution [J]. Computer Engineering and Applications, 2023, 59(2): 289-298. |
[7] | CUI Wei, ZHU Fazheng. Review of Path Planning Algorithms for Robot Navigation [J]. Computer Engineering and Applications, 2023, 59(19): 10-20. |
[8] | GAO Chengcheng, CHEN Xicheng, ZHANG Rui, SONG Qiuyue, YI Dong, WU Yazhou. Application of Three New Intelligent Algorithms in Epidemic Early Warning Model—COVID-19 Epidemic Warning Based on Baidu Search Index [J]. Computer Engineering and Applications, 2021, 57(8): 256-263. |
[9] | CHEN Lei, YIN Junsheng. Whale Swarm Optimization Algorithm Based on Gaussian Difference Mutation and Logarithmic Inertia Weight [J]. Computer Engineering and Applications, 2021, 57(2): 77-90. |
[10] | ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89. |
[11] | MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236. |
[12] | LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12. |
[13] | YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79. |
[14] | HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171. |
[15] | CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||