GRAPH COLORING ALGORITHM FOR COURSE TIME TABLE SCHEDULING PROBLEM

Ayushi Malviya; Bhawna Agrawal; Sanjeet Kumar

doi:10.29121/shodhkosh.v5.i3.2024.2182

Authors

Ayushi Malviya Department of Physical Science, Rabindranath Tagore University
Bhawna Agrawal Department of Physical Science, Rabindranath Tagore University
Sanjeet Kumar Department of Mathematics, Lakshmi Narayan College of Technology & Science, Bhopal - 400 098, Madhya Pradesh, India

DOI:

https://doi.org/10.29121/shodhkosh.v5.i3.2024.2182

Keywords:

Welch Powel, Saturated Degree, Graph Coloring

Abstract [English]

The purpose of this paper is to prepare a course time table by introducing a proposed algorithm based on known heuristic graph coloring algorithms, namely the Welch Powel algorithm and the saturation degree ordering algorithm, which found a better and optimal solution. The proposed algorithm will be used to solve the course time table scheduling problem which is formulated by converting the problem into a graph where subjects will be concede as vertices of graph.

References

Welch, D. J., & Powel, M. B. (1967). “An upper bound for the chromatic number of a graph and its application to timetabling problems”. The Computer Journal, vol.10(1),pp. 85-86. DOI: https://doi.org/10.1093/comjnl/10.1.85

Mansuri A., Gupta V. and Chandel R.S.(2010) “Coloring Programs in Graph Theory” International Journal of Math. Analysis, Vol. 4,pp. 2473 - 2479

Dahlan Abdullah (2019 )“Lecture Scheduling System Using Welch Powell Graph Coloring Algorithm in Informatics Engineering Departement of Universitas Malikussale” Journal ofPhysics: Conference Series 1363 012074 DOI: https://doi.org/10.1088/1742-6596/1363/1/012074

Peck, J. E. L., Williams, M. R.(1966).“Examination Scheduling,” Communications of the ACM, 9(6), pp.433-434. DOI: https://doi.org/10.1145/365696.365713

Wood, D. C.(1969). “A Technique for Coloring a Graph Applicable to Large Scale Timetabling Problems,” The Computer Journal, 12, pp. 317-319. DOI: https://doi.org/10.1093/comjnl/12.4.317

Johnson, D. S., Aragon, C. R., McGeoch, L. A., and Schevon, C. (1991) “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning,” Operations Research, 39(3), pp. 378-406.,The IBM Research Symposia Series, New York, NY: Plenum Press, 1972, pp. 85-103

Kiaer, L., Yellen, J. (1992). “Weighted Graphs and University Timetabling”Computers and Operations Research, 19(1), pp. 59-67. DOI: https://doi.org/10.1016/0305-0548(92)90059-E

Méndez Díaz, I., Zabala, P. (2008). A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 156(2): 159-179. DOI: https://doi.org/10.1016/j.dam.2006.07.010

Lucet, C., Mendes, F., Moukrim, A. (2006). An exact method for graph coloring. Computers & Operations Research, 33(8): 2189-207. DOI: https://doi.org/10.1016/j.cor.2005.01.008

Malviya A., Agrawal B., Kumar S.and Mansuri A., (2022) “Study of algorithm for coloring in various graph”. International Journal of Statistics and Applied Mathematics, Vol,7(2), pp.88-91.DOI: https://doi.org/10.22271/maths.2022.v7.i2b.798 DOI: https://doi.org/10.22271/maths.2022.v7.i2b.798

Segundo, P.S. (2012). A new DSATUR-based algorithm for exact vertex coloring. Computer & Operations Research, 39(7): 1724-1733. DOI: https://doi.org/10.1016/j.cor.2011.10.008

Shukla A.N. ,Bharti V. and Garag M.L. (2019), “A Link List based Exact Algorithm for Graph Coloring Problem” Revue d ’Intelligence Artificiel,33(3),pp.189-195. DOI: https://doi.org/10.18280/ria.330304

Biswas S.,Nusrat S.A.,Sharmin N.and Rahman M (2023) “ Graph Coloring in University Timetable Scheduling” I.J. Intelligent Systems and Applications, Vol .3, .pp16-32 DOI: https://doi.org/10.5815/ijisa.2023.03.02

Sunanto U.A.M., Napitupulu H., Carnia E., Supriatna A.K.(2022) “ Course Scheduling of Undergraduate Study Program of Mathematics Universitas Padjadjaran Case Using Gra Coloring with Modified Algorithm”, International Journal of Mathematics Trends and Technology, Vol. 68 pp.61-69. DOI: https://doi.org/10.14445/22315373/IJMTT-V68I1P507

Klotz, W. (2002). Graph coloring algorithms Verlag nicht ermittelbar. mathematik.tu-clausthal.de pp.1-9

Gebremedhin, A. H. (1999). Parallel graph coloring. Candidatus scientarum, University of Bergen.

Cipta H., Widyasari R.,Batubara F.H.(2023) “Graph Coloring Implementation Using Welch Powel Algorithm In Lecture Scheduling Design For mathematics Department ” M ATHLINE Journal Matematika Dan Pendidikan Matematika,Vol 8,pp1383-1398. DOI: https://doi.org/10.31943/mathline.v8i4.537

Gangrade A., Agrawal B., Kumar S. (2023). Subject Allocation Bipartite Graph coloring Samdarshi, UGCCare, Vol.16(4), pp.3128-3132.

Gangrade A., Agrawal B., Kumar S. and Mansuri A. (2022) " A study of applications of graph coloring in various fields". International Journal of Statistics and Applied Mathematics; Vol 7(2), pp. 51-53. https://doi.org/10.22271/maths.2022.v7.i2a.795. DOI: https://doi.org/10.22271/maths.2022.v7.i2a.795

Malviya A., Agrawal B., Kumar S. (2023). “A new approach on Star chromatic number of splitting complete bipartite graph” Samdarshi, UGC Care, Vol.16(5), pp.2581-3986.