A Quantum-Inspired Evolutionary and IPSO Hybrid Model For Efficient Graph Colouring Under Multi-Constraint Conditions

Abstract

Graph colouring, a fundamental problem in combinatorial optimization, plays a critical role in various real-world applications such as register allocation, scheduling, and frequency assignment. Efficiently solving the graph colouring problem under multiple constraints remains a major computational challenge, particularly for large and complex graphs. This study addresses these limitations by proposing a hybrid optimization model that integrates Quantum-Inspired Evolutionary Algorithms (QIEA) with an Improved Particle Swarm Optimization (IPSO) technique. The proposed model leverages the probabilistic representation and parallel search capabilities of QIEA along with the adaptive learning and velocity adjustment features of IPSO to explore the solution space effectively. The primary objective is to minimize the number of colours used while satisfying adjacency, capacity, and dependency constraints. Experimental evaluations conducted on benchmark graph instances demonstrate that the hybrid model significantly outperforms existing evolutionary and heuristic methods in terms of convergence speed, constraint satisfaction, and colouring efficiency. These results affirm the potential of the QIEA-IPSO hybrid in solving complex multi-constrained graph colouring problems.