Abstract
Planar graph coloring is a classic NP - hard problem. So far there is no completely effective method to solve this problem. This paper presents a discrete artificial electric field algorithm to solve the graph coloring problem. The algorithm first codes according to the graph coloring problem to meet the requirements of the graph coloring problem, and then adds part of local search to improve the performance of the algorithm. The algorithm can effectively and accurately solve the coloring problem of plane graphs. Compared with several classical algorithms, the results show that the proposed algorithm has a smaller average number of iterations and a higher success rate in dealing with graph coloring problems, and it can also find the correct coloring scheme in real map problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barman, S.C., Pal, M., Mondal, S.: An optimal algorithm to find minimum k-hop dominating set of interval graphs. Discrete Math. Algorithms Appl. 11(3), 1950016 (2018)
Bhosale, B., Ahmed, B., Biswas, A.: On wavelet based modeling of neural networks using graph theoretic approach. Life Sci. J. 10(2), 1509–1515 (2013)
Burke, E.K., et al.: A graph-based hyper-heuristic for educational timetabling problems. Eur. J. Oper. Res. 176, 177–192 (2007)
Giaro, K., Kubale, M., Obszarski, P.: A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints. Discrete Appl. Math. 157(17), 3625–3630 (2009)
Hao, J.K., Dorne, R., Galinier, P.: Tabu search for frequency assignment in mobile radio networks. J. Heuristics 4(1), 47–62 (1998)
Anita, Yadav, A.: AEFA: artificial electric field algorithm for global optimization. Swarm Evol. Comput. 48, 93–108 (2019)
Anita, Yadav, A.: Discrete artificial electric field algorithm for high-order graph matching. Appl. Soft Comput. 92, 106260 (2020)
Sajwan, A., Yadav, A., Kumar, N., et al.: Development of discrete artificial electric field algorithm for quadratic assignment problems. In: Nigdeli, S.M., Kim, J.H., Bekdaş, G., Yadav, A. (eds.) ICHSA 2020. AISC, vol. 1275, pp. 411–421. Springer, Singapore (2021). https://doi.org/10.1007/978-981-15-8603-3_36
Demirren, A., et al.: Opposition-based artificial electric field algorithm and its application to FOPID controller design for unstable magnetic ball suspension system. Eng. Sci. Technol. Int. J. 24(2), 469–479 (2020)
Sajwan, A., Yadav, A.: An intelligent model for the detection of white blood cells using artificial intelligence. Comput. Methods Programs Biomed. 199(10), 105893 (2021)
Anita, Yadav, A., Kumar, N.: Application of artificial electric field algorithm for economic load dispatch problem. In: Abraham, A., Jabbar, M., Tiwari, S., Jesus, I. (eds.) SoCPaR 2019. AISC, vol. 1182, pp. 71–79. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-49345-5_8
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: ICNN 1995-International Conference on Neural Networks. IEEE (1995)
Qin, A.K., Huang, V.L., Suganthan, P.N.: Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. Evol. Comput. 13(2), 398–417 (2009)
Valdez, F., Melin, P., Castillo, O.: An improved evolutionary method with fuzzy logic for combining particle swarm optimization and genetic algorithms. Appl. Soft Comput. 11, 2625–2632 (2011)
Jiao, W., Liu, G., Liu, D.: Elite particle swarm optimization with mutation. IEEE (2011)
Yang, X.-S.: Flower pollination algorithm for global optimization. In: Durand-Lose, J., Jonoska, N. (eds.) UCNC 2012. LNCS, vol. 7445, pp. 240–249. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32894-7_27
Acknowledgment
This work is supported by National Science Foundation of China under Grants No. U21A20464, 62066005.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yu, Y., Zhou, Y., Luo, Q., Wei, X. (2022). Discrete Artificial Electric Field Optimization Algorithm for Graph Coloring Problem. In: Huang, DS., Jo, KH., Jing, J., Premaratne, P., Bevilacqua, V., Hussain, A. (eds) Intelligent Computing Methodologies. ICIC 2022. Lecture Notes in Computer Science(), vol 13395. Springer, Cham. https://doi.org/10.1007/978-3-031-13832-4_70
Download citation
DOI: https://doi.org/10.1007/978-3-031-13832-4_70
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-13831-7
Online ISBN: 978-3-031-13832-4
eBook Packages: Computer ScienceComputer Science (R0)