Arrêt de service lundi 11 juillet de 12h30 à 13h : tous les sites du CCSD (HAL, EpiSciences, SciencesConf, AureHAL) seront inaccessibles (branchement réseau à modifier)
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03700895
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mardi 21 juin 2022 - 14:58:18
Dernière modification le : mercredi 22 juin 2022 - 03:06:26

Identifiants

  • HAL Id : hal-03700895, version 1

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

0