Considération des motifs dans la détermination d'une borne supérieure de la force d'un graphe
Résumé
The Minimum Sum Colouring Problem (MSCP) is a vertex colouring problem with a weight associated to each colour. The aim of the MSCP is to find an optimal colouring of the vertices of a graph G with the mini mum sum of the associated weights of the used colours. The MSCP has important applications in fields such as scheduling and VLSI design. The minimum number of colours in an optimal solution of the MSCP for G is called the chromatic strength of G and is denoted by s(G). Tight upper bounds of s(G) allow to significantly reduce the search space when solving the MSCP. In this paper, we propose two new upper bounds, UBA and UBS, of s(G) for general graphs based on an abstraction of all possible colourings of G formulated as an ordered set of non-increasing positive integer sequences. The results of experiments on the standard benchmarks DiMACS and COLOR show that our new bounds are significantly Papier doctorant : Clément Lecat est auteur principal. tighter than those previously published in the literature : UBS improves the upper bound for 70 graphs out of 74.