Séminaire passé

01 juin 2017 par J. Guo : A partition-based exact method for graph coloring problem and its application to dynamic resource allocation

Résumé :

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.


  1. Games

    Séminaire passé | OPERA

    Pretty component to content. I simply stumbled upon your website and in accession capital to say that I acquire in fact enjoyed account your blog posts. Any way I’ll be subscribing on your augment or even I achievement you access persistently fast.

  2. Blackjack

    Séminaire passé | OPERA

    Someone necessarily help to make critically articles I might state. This is the first time I frequented your web page and so far? I amazed with the research you made to create this actual submit amazing. Fantastic process!