Swapnil Biswas

Work place: Department of Computer Science and Engineering, Military Institute of Science and Technology Mirpur Cantonment, Dhaka 1216

E-mail: swapnil.cse16@gmail.com


Research Interests: Data Structures and Algorithms, Data Structures


Swapnil Biswas, Lecturer, department of Computer Science and Engineering at Mil- itary Institute of Science and Technology (MIST) was born in Dhaka, Bangladesh in 1998. He rcompleted his B.Sc. in Computer Science and Engineering from Military Institute of Science and Technology (MIST), Dhaka, Bangladesh. Currently he is pursuing his M.Sc. in Computer Science and Engineering from the same institution. His interest in research includes Graph Theory, Data Structures and Algorithms.

Author Articles
Graph Coloring in University Timetable Scheduling

By Swapnil Biswas Syeda Ajbina Nusrat Nusrat Sharmin Mahbubur Rahman

DOI: https://doi.org/10.5815/ijisa.2023.03.02, Pub. Date: 8 Jun. 2023

Addressing scheduling problems with the best graph coloring algorithm has always been very challenging. However, the university timetable scheduling problem can be formulated as a graph coloring problem where courses are represented as vertices and the presence of common students or teachers of the corresponding courses can be represented as edges. After that, the problem stands to color the vertices with lowest possible colors. In order to accomplish this task, the paper presents a comparative study of the use of graph coloring in university timetable scheduling, where five graph coloring algorithms were used: First Fit, Welsh Powell, Largest Degree Ordering, Incidence Degree Ordering, and DSATUR. We have taken the Military Institute of Science and Technology, Bangladesh as a test case. The results show that the Welsh-Powell algorithm and the DSATUR algorithm are the most effective in generating optimal schedules. The study also provides insights into the limitations and advantages of using graph coloring in timetable scheduling and suggests directions for future research with the use of these algorithms.

[...] Read more.
Other Articles