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.
Accepté le :
DOI : 10.1051/ro/2016069
Mots-clés : Chromatic number, graph orientation, graph coloring, team building, healthcare
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2016069/
[1] , , , , , and , Workforce management based on forecasted demand, in Advanced Decision Making Methods Applied to Health Care. Springer Milan (2012) 1–11
[2] , A nurse scheduling using graph colouring, Master dissertation, Kwame Nkrumah University of Science and Technology (2013)
[3] , and , Bounding χ in terms of ω and Δ for some classes of graphs. Discrete Math. 311 (2011) 911–920 | DOI | MR | Zbl
[4] , Composing medical crews with equity and efficiency. Central Eur. J. Oper. Res. 17 (2009) 343–357 | DOI | MR | Zbl
[5] and A 0-1 Goal Programming Model for Nurse Scheduling. Comput. Oper. Res. 32 (2005) 491–507 | DOI | MR | Zbl
[6] , , , and , Oriented trees in digraphs. Discrete Math. 313 (2013) 967–974 | DOI | MR | Zbl
[7] , On colouring the nodes of a network. Math. Proc. of Cambridge Philosophical Society 37 (1941) 194–197 | DOI | JFM | MR | Zbl
[8] , , and The state of the art of nurse rostering. J. Sched. 7 (2004) 441–499 | DOI | MR | Zbl
[9] , , and , Nurse rostering problems – a bibliographic survey. Eur. J. Oper. Res. 151 (2003) 447–460 | DOI | MR | Zbl
[10] , , , , and , Team composition optimization: The Team Optimal Profile System (TOPS). ARI Technical Review, Alexandria, VA: U.S. Army Research Institute for the Behavioral and Social Sciences (2009)
[11] , and , Multi-objective optimization and decision making approaches to cricket team selection. Appl. Soft Comput. 13 (2013) 402–414 | DOI
[12] , and Two bounds of chromatic number in graphs coloring problem. In: CoDIT International Conference on Control, Decision and Information Technologies (2014) 292–296
[13] , H. Ait haddadene and A. Nagih, A labeling order scheme for the maximum clique problem. Appl. Math. Sci. 6 (2012) 5439–5452 | MR | Zbl
[14] and , Graph coloring problems, Wiley, New York (1995) | MR | Zbl
[15] , Reducibility among combinatorial problems. Complexity of computercomputation 1972 | DOI | MR | Zbl
[16] , and , A characterization of graphs with fractional total chromatic number equal to Δ + 2. Electronic Notes in Discrete Math. 35 (2009) 235–240 | DOI | MR | Zbl
[17] and , The chromatic number of graphs which induce neither K1,3 nor K5 −e. Discrete Math. 58 (1986) 253–262 | DOI | MR | Zbl
[18] and , Bounding χ in terms of ω and Δ for quasi-line graphs. J. Graph Theory 59 (2008) 215–228 | DOI | MR | Zbl
[19] , and , An upper bound for the chromatic number of line graphs. Eur. J. Combin. 28 (2007) 2182–2187 | DOI | MR | Zbl
[20] and , Some results on Reed’s Conjecture about ω, Δ and χ with respect to α. Discrete Math. 310 1429–1438 (2010) | DOI | MR | Zbl
[21] , and , Graphs with chromatic number close to maximum degree. Discrete Math. 312 (2012) 1273–1281 | DOI | MR | Zbl
[22] and , An upper bound on the domination number of n-vertex connected cubic graphs. Discrete Mathematics 309 (2009) 1142–1162 | DOI | MR | Zbl
[23] and , Automated system for nurse scheduling using Graph Colouring. Indian J. Comput. Sci. Eng. 2 (2011) 476–485
[24] , Planification de personnel avec affectation de taches fixées: méthodes et application dans un contexte médical. Ph.D. thesis, University of Nantes (2014)
[25] , , , and , Choosability of graphs with bounded order: Ohba’s conjecture and beyond. Electr. Notes Discr. Math. 43 (2013) 89–95 | DOI
[26] , A note on Reed’s conjecture. SIAM J. Discrete Math. 22 (2008) 820–827 | DOI | MR | Zbl
[27] , ω, Δ, and χ. J. Graph Theory 27 (1998) 177–212 | DOI | MR | Zbl
[28] , A new upper bound for the chromatic number of a graph. Discuss. Math. Graph Theory 27 (2007) 137–142 | DOI | MR | Zbl
[29] , A team building model for software engineering courses term projects. Comput. Education 56 (2011) 916–922 | DOI
[30] and , Hybrid Optimization Techniques for the Workshift and Rest Assignment of Nursing Personnel. Artificial Intelligence in Medicine 20 (2000) 155–175 | DOI
Cité par Sources :
