New Adaptive Parallel Evolutionary Approach for Graph Coloring and Channel Allocation
Main Article Content
Abstract
Graph coloring is a Nondeterministic Polynomial-time (NP)-hard problem with wide applications; existing evolutionary methods suffer from fixed operators, premature convergence, and prolonged computation on large graphs. This research aims to minimize the number of colors and conflicting edges while reducing generations and runtime for large-scale graph coloring and channel allocation. Research proposes a decentralized island-based memetic framework in which independent-set extraction reduces the original graph, while a clique-split strategy lowers interference in channel allocation, and greedy initialization seeds diverse subpopulations. This framework evolves subpopulations concurrently on multiple processors, by exchanging elite individuals through periodic migration to preserve diversity. Adaptive probability matching selects crossover and mutation operators according to conflict-reduction success, and tabu search refines offspring. A fixed-k strategy iteratively decrements k after each conflict-free coloring. In graph coloring, vertices are partitioned into minimal independent color classes; in channel allocation, wireless nodes form a conflict graph in which colors represent frequencies, and cliques determine the minimal interference-free channel requirement. This approach combines class-preserving crossover, conflict-directed mutation, and statistics-driven operator selection, thereby reducing the search space while sustaining exploration across islands and accelerating convergence toward feasible colorings. Experiments on Discrete Mathematics and Theoretical Computer Science (DIMACS) graph-coloring benchmarks and wireless Channel Assignment Problem (CAP) instances achieve competitive color counts of 5–84, computation times of 0.09-15.72 s, and success rates of 78-96%, while demonstrating effective conflict minimization and convergence across varying allocation scenarios in CAP. Overall, it provides a scalable and efficient solution for large-scale graph coloring and channel allocation, also extensible to other engineering applications.
Keywords: G, , , , ,
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
References
Gimenez-Guzman, J.M., Marsa-Maestre, I., de la Hoz, E., Orden, D. and Herranz-Oliveros, D., 2023. Channel selection in uncoordinated IEEE 802.11 networks using graph coloring. Sensors, 23(13), p.5932. https://doi.org/10.3390/s23135932
Terci, G.S. and Boz, B., 2025. Coloring dynamic graphs with a similarity and pool-based evolutionary algorithm. IEEE Access, 13, pp.38054-38075. https://doi.org/10.1109/ACCESS.2025.3546108
Ge, C., Xia, S., Chen, Q. and Adachi, F., 2022. 2-layer interference coordination framework based on graph coloring algorithm for a cellular system with distributed MU-MIMO. IEEE Transactions on Vehicular Technology, 72(3), pp.3557-3568. https://doi.org/10.1109/TVT.2022.3219411
Švarcmajer, M., Ivanović, D., Rudec, T. and Lukić, I., 2025. Application of graph theory and variants of greedy graph coloring algorithms for optimization of distributed peer-to-peer blockchain networks. Technologies, 13(1), p.33. https://doi.org/10.3390/technologies13010033
Sun, K., Zhang, J., Gao, X., Huang, W., Zhang, H. and Leung, V.C., 2024. Dynamic channel allocation scheme based on traffic prediction in dense wireless networks. IEEE Transactions on Wireless Communications, 23(9), pp.12331-12342. https://doi.org/10.1109/TWC.2024.3391426
Lee, W. and Seo, J.B., 2023. Deep learning-aided channel allocation scheme for wlan. IEEE Wireless Communications Letters, 12(6), pp.1007-1011. https://doi.org/10.1109/LWC.2023.3257128
Ascoli, A., Weiher, M., Herzig, M., Slesazeck, S., Mikolajick, T. and Tetzlaff, R., 2022. Graph coloring via locally-active memristor oscillatory networks. Journal of Low Power Electronics and Applications, 12(2), p.22. https://doi.org/10.3390/jlpea12020022
Zhou, B., Li, S., Zi, B., Chen, B. and Zhu, W., 2023. Multi-objective optimal design of a cable-driven parallel robot based on an adaptive adjustment inertia weight particle swarm optimization algorithm. Journal of Mechanical Design, 145(8), p.083301. https://doi.org/10.1115/1.4062458
Mansour, R.F., Abdel-Khalek, S., Basha, S.M., Khayyat, M.M., Elnaim, B.M. and Shankar, V., 2022. Adaptive Parallel Seeker Optimization-based Route Planning for clustered WSN in smart cities. Computers and Electrical Engineering, 102, p.108289. https://doi.org/10.1016/j.compeleceng.2022.108289
Mosavi, S.A.A., Erfanian, A. and Sabeghi, N., 2026. Design and implementation of a graph-coloring algorithm for optimizing flight-level allocation in air traffic management in Iran. Iranian Journal of Numerical Analysis & Optimization, 16(2), p.590. https://doi.org/10.22067/ijnao.2026.95911.1749
Yakut, S., 2025. Efficient and robust graph coloring algorithm for graph coloring problem: Malatya vertex coloring algorithm. IEEE Access, 13, pp.168512 - 168526. https://doi.org/10.1109/ACCESS.2025.3614296
Kralev, V. and Kraleva, R., 2023. A comparative analysis between two heuristic algorithms for the graph vertex coloring problem. International Journal of Electrical and Computer Engineering (IJECE), 13(3), p.2981. https://doi.org/10.11591/ijece.v13i3.pp2981-2989
Marappan, R. and Sethumadhavan, G., 2022. Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization. Arabian Journal for Science and Engineering, 47(8), pp.9695-9712. https://doi.org/10.1007/s13369-021-06323-x
Gao, M. and Hu, J., 2024. Graph coloring algorithm based on minimal cost graph neural network. IEEE Access, 12, pp.168000-168009. https://doi.org/10.1109/ACCESS.2024.3439352
Sano, Y., Norimoto, M. and Ishikawa, N., 2023. Qubit reduction and quantum speedup for wireless channel assignment problem. IEEE Transactions on Quantum Engineering, 4, pp.1-12. https://doi.org/10.1109/TQE.2023.3293452
Shahryari, M.S., Farzinvash, L., Feizi-Derakhshi, M.R. and Taherkordi, A., 2023. High-throughput and energy-efficient data gathering in heterogeneous multi-channel wireless sensor networks using genetic algorithm. Ad Hoc Networks, 139, p.103041. https://doi.org/10.1016/j.adhoc.2022.103041
Logeshwaran, J., Shanmugasundaram, R.N. and Lloret, J., 2024. Load based dynamic channel allocation model to enhance the performance of device-to-device communication in WPAN. Wireless Networks, 30(4), pp.2477-2509. https://doi.org/10.1007/s11276-024-03680-x