New hybrid decentralized evolutionary approach for DIMACS challenge graph coloring & wireless network instances

Abstract

The Graph Coloring Problem is an NP-hard combinatorial optimization problem, and it is being used in different real-world environments. The chromatic integer is determined using different probabilistic methods. This paper explores a new hybrid decentralized evolutionary approach that applies the fixed colors and reduces the edge conflicts iteratively using greedy, split and conquer strategies. This article explores a new hybrid decentralized stochastic methodology for solving graph coloring. The method is constructed by combining the following strategies: Greedy heuristics, split & conquer, and decentralized strategy with an advanced & enhanced global search evolutionary operator. These hybrid design strategies are exhibited on complex DIMACS challenge benchmark graphs and wireless network instances. The proposed approach minimizes the complexity and converges to the optimal solution within a minimal time. The minimum percentage of successful runs obtained for the DIMACS benchmarks lies in (82%, 85%) except for the difficult instance latin_square_10.col, the vertices count n = 900 and edges count m = 307350. For the latin_square_10.col graph, the minimum color is reduced to 97 compared to other methods with less successful runs percentage. For the difficult instance flat1000_76_0.col graph, the minimum color is reduced to 76 compared to other methods, resulting in a better successful run. The method obtains the minimum color as χ(G) for the difficult instances le.col and flat.col graphs compared to other methods. The time taken to execute the developed technique is compared with the competing methods, and the proposed method outperforms very competitively in finding the minimum color for large graphs and also in finding the better solution with the high frequency of convergence (> 98%) in the channel allocation of wireless networks compared to the current methods.

Keywords

• Channel allocation
• Chromatic number
• Combinatorial optimization
• Divide and conquer
• Evolutionary operators
• Graph coloring