New approximation algorithms for solving graph coloring problem – An experimental approach

Publication date: Available online 30 April 2016 Source:Perspectives in Science Author(s): Raja Marappan, Gopalakrishnan Sethumadhavan, R.K. Srihari Some of the real world applications require the solution to graph coloring problem, an NP-hard combinatorial optimization problem. χ(G), the chromatic number of a graph G, the minimum number of colors required to color the vertex set V(G) with adjacent vertices assigned with different color can also be obtained using evolutionary methods. This paper exhibits two new approximation methods of solving graph coloring based on μ ½(G), the median of the degrees V(G). In the first method, a heuristic procedure is designed to color V(G) which works in two stages. In the first stage, to minimize the conflicting edges, the vertices of V(G) whose degrees are ≥μ ½(G) are colored. Then the remaining vertices are colored through a heuristic procedure. The second method is implemented using divide & conquer strategy. These new approximation algorithms are exhibited on some of the small, intermediate and large benchmark graphs and the results are compared. The proposed algorithms significantly reduce the computational complexity in obtaining the near optimal solution and also the results are found to be better than the existing approaches.

Source: Perspectives in Science - May 30, 2016 Category: Science Source Type: research