Considération des motifs dans la détermination d'une borne supérieure de la force d'un graphe - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Considération des motifs dans la détermination d'une borne supérieure de la force d'un graphe

, (1) , (1)
1
C. Lecat
  • Fonction : Auteur

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.
Fichier non déposé

Dates et versions

hal-03700895 , version 1 (21-06-2022)

Identifiants

  • HAL Id : hal-03700895 , version 1

Citer

C. Lecat, Corinne Lucet, Chu-Min Li. Considération des motifs dans la détermination d'une borne supérieure de la force d'un graphe. Treiziemes Journees Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. pp.177--186. ⟨hal-03700895⟩
3 Consultations
0 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More