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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016069
Classification : 05C85, 68R10
Mots clés : Chromatic number, graph orientation, graph coloring, team building, healthcare
Gueham, Assia 1 ; Nagih, Anass 1 ; Haddadene, Hacene Ait 1 ; Masmoudi, Malek 1

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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2016069/

[1] B. Addis, R. Aringhieri, G. Carello, A. Grosso, F. Maffioli, E. Tanfani and A. Testi, Workforce management based on forecasted demand, in Advanced Decision Making Methods Applied to Health Care. Springer Milan (2012) 1–11

[2] G. Anane, A nurse scheduling using graph colouring, Master dissertation, Kwame Nkrumah University of Science and Technology (2013)

[3] N.R. Aravind, T. Kartchik and C.R. Subramanian, Bounding χ in terms of ω and Δ for some classes of graphs. Discrete Math. 311 (2011) 911–920 | DOI | MR | Zbl

[4] R. Aringhieri, Composing medical crews with equity and efficiency. Central Eur. J. Oper. Res. 17 (2009) 343–357 | DOI | MR | Zbl

[5] M.N. Azaiez and S.S. Al Sharif A 0-1 Goal Programming Model for Nurse Scheduling. Comput. Oper. Res. 32 (2005) 491–507 | DOI | MR | Zbl

[6] L.A. Berry, F. Havet, C.L. Sales, B. Reed and S. Thomasse, Oriented trees in digraphs. Discrete Math. 313 (2013) 967–974 | DOI | MR | Zbl

[7] R.L. Brooks, On colouring the nodes of a network. Math. Proc. of Cambridge Philosophical Society 37 (1941) 194–197 | DOI | JFM | MR | Zbl

[8] E.K. Burke, P. De Causmaecker, G.V. Berghe and H. Van Landeghem The state of the art of nurse rostering. J. Sched. 7 (2004) 441–499 | DOI | MR | Zbl

[9] B. Cheang, H. Li, A. Lim and B. Rodrigues, Nurse rostering problems – a bibliographic survey. Eur. J. Oper. Res. 151 (2003) 447–460 | DOI | MR | Zbl

[10] J.S. Donsbach, S.I. Tannenbaum, G.A. Alliger, J.E. Mathieu, E. Salas and G.F. Goodwin, 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] A. Faez, D. Kalyanmoy and J. Abhilash, Multi-objective optimization and decision making approaches to cricket team selection. Appl. Soft Comput. 13 (2013) 402–414 | DOI

[12] A. Gueham, A. Nagih and H. Ait Haddadene Two bounds of chromatic number in graphs coloring problem. In: CoDIT International Conference on Control, Decision and Information Technologies (2014) 292–296

[13] A. Gueham, 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] T. Jensen and B. Toft, Graph coloring problems, Wiley, New York (1995) | MR | Zbl

[15] R.M. Karp, Reducibility among combinatorial problems. Complexity of computercomputation 1972 | DOI | MR | Zbl

[16] T. Ito, W.S. Kennedy and B.A. Reed, 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] H.A. Kierstead and J.H. Schmerl, The chromatic number of graphs which induce neither K1,3 nor K5 −e. Discrete Math. 58 (1986) 253–262 | DOI | MR | Zbl

[18] A.D. King and B.A. Reed, Bounding χ in terms of ω and Δ for quasi-line graphs. J. Graph Theory 59 (2008) 215–228 | DOI | MR | Zbl

[19] A.D. King, B.A. Reed and A. Vetta, An upper bound for the chromatic number of line graphs. Eur. J. Combin. 28 (2007) 2182–2187 | DOI | MR | Zbl

[20] A. Kohl and I. Schiermeyer, Some results on Reed’s Conjecture about ω, Δ and χ with respect to α. Discrete Math. 310 1429–1438 (2010) | DOI | MR | Zbl

[21] A.V. Kostochka, L. Rabern and M. Stiebitz, Graphs with chromatic number close to maximum degree. Discrete Math. 312 (2012) 1273–1281 | DOI | MR | Zbl

[22] A.V. Kostochka and B.Y. Stodolsky, An upper bound on the domination number of n-vertex connected cubic graphs. Discrete Mathematics 309 (2009) 1142–1162 | DOI | MR | Zbl

[23] B.T.G.S. Kumara and A.A.I. Perera, Automated system for nurse scheduling using Graph Colouring. Indian J. Comput. Sci. Eng. 2 (2011) 476–485

[24] T. Lapegue, 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] J.A. Noel, B.A. Reed, D.B. West, H. Wu and X. Zhu, Choosability of graphs with bounded order: Ohba’s conjecture and beyond. Electr. Notes Discr. Math. 43 (2013) 89–95 | DOI

[26] L. Rabern, A note on Reed’s conjecture. SIAM J. Discrete Math. 22 (2008) 820–827 | DOI | MR | Zbl

[27] B. Reed, ω, Δ, and χ. J. Graph Theory 27 (1998) 177–212 | DOI | MR | Zbl

[28] I. Schiermeyer, A new upper bound for the chromatic number of a graph. Discuss. Math. Graph Theory 27 (2007) 137–142 | DOI | MR | Zbl

[29] Y.G. Sahin, A team building model for software engineering courses term projects. Comput. Education 56 (2011) 916–922 | DOI

[30] C. Valouxis and E. Housos, Hybrid Optimization Techniques for the Workshift and Rest Assignment of Nursing Personnel. Artificial Intelligence in Medicine 20 (2000) 155–175 | DOI

Cité par Sources :