Graph Coloring Study Applied to the Timetable Allocation Problem: A Student-Focused Solution

• François Barbosa UFPI
• José Jeovane UFPI
• Guilherme Avelino UFPI
• Arlino Magalhães UFPI

DOI: https://doi.org/10.5753/ercemapi.2024.243698

Abstract

The research explores the application of Graph Theory to the problem of timetable allocation, focusing on students in their final year. Using graph coloring, subjects were represented as vertices and students as edges. Two main approaches were compared: the Brute Force algorithm and the Degree of Saturation (DSATUR) heuristic. The results showed that although the Brute Force algorithm provides an optimal solution, it is computationally expensive. In contrast, the DSATUR heuristic proved to be extremely efficient in terms of execution time, although it does not always guarantee the optimal solution. The code for the proposed application is available at Google Colab.

References

Bagheri, E., Noia, T. D., Gasevic, D., and Ragone, A. (2012). Formalizing interactive staged feature model configuration. Journal of Software: Evolution and Process, 24(4):375–400.

Blum, A. (1994). New approximation algorithms for graph coloring. J. ACM, 41(3):470–516.

de Werra, D. (1990). Heuristics for Graph Coloring, pages 191–208. Springer Vienna, Vienna.

Duarte, I., Cancela, L., and Rebola, J. (2021). Graph coloring heuristics for optical networks planning. In 2021 Telecoms Conference (ConfTELE), pages 1–6.

Egwuche, O. S. (2020). Examination timetabling with graph coloring for emerging institutions. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS), pages 1–6.

Hussin, B., Basari, A. S. H., Shibghatullah, A. S., Asmai, S. A., and Othman, N. S. (2011). Exam timetabling using graph colouring approach. In 2011 IEEE Conference on Open Systems, pages 133–138.

Jensen, T. and Toft, B. (2011). Graph Coloring Problems. Wiley Series in Discrete Mathematics and Optimization. Wiley.

LABED, S., KOUT, A., and CHIKHI, S. (2018). A fast heuristic for graph b-coloring problem. In 2018 JCCO Joint International Conference on ICT in Education and Training, International Conference on Computing in Arabic, and International Conference on Geocomputing (JCCO: TICET-ICCA-GECO), pages 1–6.

Pillay, N. (2013). A comparative study of hyper-heuristics for solving the school timetabling problem. In Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, SAICSIT ’13, page 278–285, New York, NY, USA. Association for Computing Machinery.

Streicher, S. and du Preez, J. (2017). Graph coloring: Comparing cluster graphs to factor graphs. In Proceedings of the ACM Multimedia 2017 Workshop on South African Academic Participation, SAWACMMM ’17, page 35–42, New York, NY, USA. Association for Computing Machinery.

Tuza, Z. (1997). Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17(2):161–228.