01 juin 2017 par J. Guo : A partition-based exact method for graph coloring problem and its application to dynamic resource allocation
Graph coloring problem is a well-known traditional NP-complete problem and designing effective exact algorithms for it is still an interesting topic. By analyzing the graph structure, an exact algorithm called TexaCol is proposed which is capable of getting all solutions of the legal k-coloring for a graph G as well as the chromatic polynomial of G. The algorithm includes three steps: the maximal clique decomposition, the suite construction and the vertices coloring. Furthermore, two exact graph coloring algorithms, PexaCol and AexaCol, have been designed, which are able to obtain partial best solutions and all best solutions of G respectively. Finally, on the basis of these static methods, a dynamic graph coloring algorithm is proposed to effectively solve the dynamic cluster resource assignment problem for Device-to-Device networks. The results show that this dynamic algorithm has good performance in resource utilization, runtime and scalability.