EXAMINATION SCHEDULER USING A LINEAR-TIME GRAPH COLORING ALGORITHM

Abstract
The primary aim of the study aims to provide a solution for scheduling examinations for most of the universities and colleges across India which follow the Choice Based Credit System (CBCS) using a graph coloring algorithm. Nowadays, due to the flexibility of opting various subjects, and many students taking up different courses in their colleges and universities, it becomes difficult to schedule these examinations. Creating an examination schedule can be quite challenging and time-consuming for controlling the body of an examination. Our research work focuses on reducing the efforts for scheduling such examinations. With the knowledge of graph theory and graph traversing and coloring algorithms, our algorithm with the help of a few assumptions gives an efficient solution to the examination scheduling problem. A detailed correctness proof along with performance analysis has been done. The efficiency of our proposed algorithm is then compared to that of the coloring algorithm using backtracking.

Authors
Debabrata Datta, Rush Guha, Neelabha Banerjee, Sohan Adhikary and Anal Acharya
St. Xavier’s College, India1,2,3,4,5

Keywords
Examination Scheduling, Graph Coloring Algorithm, Bipartite Graphs, NP-Complete Problem, Linear Time Complexity, Meta-Graph
Published By :
ICTACT
Published In :
ICTACT Journal on Soft Computing
( Volume: 12 , Issue: 4 )
Date of Publication :
July 2022
DOI :

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.