Towards Efficient Heuristic Graph Edge Coloring

Graph edge coloring problem is a branch of the graph coloring problem and is a classic NP-hard problem in graph theory. The goal of edge coloring is to minimize the number of colors used for coloring such that any two adjacent edges are not the same color. Due to its NP-Hardness, we focus on the efficient ordering heuristics for the graph edge coloring in this paper. We systematically explore six different orderings which have been shown to significantly influence the effectiveness of the vertex coloring. Different from the vertex coloring, our experimental results demonstrate that these heuristic orderings have little effect on the graph edge coloring results and almost all these orderings can obtain nearly-optimal coloring results. Meanwhile, considering parallel graph edge coloring presents an interesting challenge for algorithm developers, we design a parallel edge coloring algorithm based on predecessor edges and successor edges. Moreover, we further design a partitioning-based method to address the oversized memory consumption problem of the proposed parallel algorithm. We evaluate our proposed algorithms and the experimental results demonstrate the effectiveness and efficiency of our proposed algorithm.