Voir la notice de l'article provenant de la source Numdam
In this paper, we focus on the coloration approach and estimation of chromatic number. First, we propose an upper bound of the chromatic number based on the orientation algorithm described in previous studies. This upper bound is further improved by developing a novel coloration algorithm. Second, we make a theoretical and empirical comparison of our bounds with Brooks’s bound and Reed’s conjecture for class of triangle-free graphs. Third, we propose an adaptation of our algorithm to deal with the team building problem respecting several hard and soft constraints. Finally, a real case study from healthcare domain is considered for illustration.
Gueham, Assia 1 ; Nagih, Anass 1 ; Haddadene, Hacene Ait 1 ; Masmoudi, Malek 1
@article{RO_2018__52_3_807_0,
author = {Gueham, Assia and Nagih, Anass and Haddadene, Hacene Ait and Masmoudi, Malek},
title = {Graph coloring approach with new upper bounds for the chromatic number: team building application},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {807--818},
publisher = {EDP-Sciences},
volume = {52},
number = {3},
year = {2018},
doi = {10.1051/ro/2016069},
mrnumber = {3868446},
zbl = {1403.05046},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016069/}
}
TY - JOUR AU - Gueham, Assia AU - Nagih, Anass AU - Haddadene, Hacene Ait AU - Masmoudi, Malek TI - Graph coloring approach with new upper bounds for the chromatic number: team building application JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 807 EP - 818 VL - 52 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016069/ DO - 10.1051/ro/2016069 LA - en ID - RO_2018__52_3_807_0 ER -
%0 Journal Article %A Gueham, Assia %A Nagih, Anass %A Haddadene, Hacene Ait %A Masmoudi, Malek %T Graph coloring approach with new upper bounds for the chromatic number: team building application %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 807-818 %V 52 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016069/ %R 10.1051/ro/2016069 %G en %F RO_2018__52_3_807_0
Gueham, Assia; Nagih, Anass; Haddadene, Hacene Ait; Masmoudi, Malek. Graph coloring approach with new upper bounds for the chromatic number: team building application. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 3, pp. 807-818. doi: 10.1051/ro/2016069
Cité par Sources :