Open Access
Subscription Access
Open Access
Subscription Access
Examination Scheduler Using a Linear - Time Graph Coloring Algorithm
Subscribe/Renew Journal
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.
Keywords
Examination Scheduling, Graph Coloring Algorithm, Bipartite Graphs, NP-Complete Problem, Linear Time Complexity, Meta-Graph
Subscription
Login to verify subscription
User
Font Size
Information
- F. Harary, “Graph Theory”, Addison-Wesley Publishing Company, 2001.
- M. Malkawi, M.A.H. Hassan and O.A.H. Hassan, “A New Exam Scheduling Algorithm using Graph Coloring”, International Arab Journal of Information Technology, Vol. 5, No. 1, pp. 1-14, 2008.
- A. Akbulut and G. Yilmaz, “University Exam Scheduling System using Graph Coloring Algorithm and RFID Technology”, International Journal of Innovation, Management and Technology, Vol. 4, pp. 66-78, 2013.
- M. Bharti and R. Kumar, “Better Resource Utilization in Exam Scheduling using Graph Coloring”, Ph.D. Dissertations, Department of Computer Science and Engineering, Thapar University, pp. 1-57, 2012.
- D. Konig, “The Infinite and Infinite Graphs”, Reprinted Chelsea, 1950.
- J.D. Ullman, “NP-Complete Scheduling Problems”, Journal of Computer and System Sciences, Vol. 10, pp. 384-393, 1975.
- N.K. Mehta, “The Application of A Graph Coloring Method to An Examination Scheduling Problem”, Interfaces, Vol. 11, pp. 57-65, 1981.
- R. Ganguli and S. Roy, “A Study on Course Timetable Scheduling using Graph Coloring Approach”, International Journal of Computational and Applied Mathematics, Vol. 12, pp. 469-485, 2017.
- F.T. Ceighton, “A Graph Coloring Algorithm for Large Scheduling Problems”, Journal of Research of The National Bureau of Standards, Vol. 84, pp. 489-506. 1979.
- D. West, “Introduction to Graph Theory”, Prentice Hall, 2001.
- C.L. Liu, “Elements of Discrete Mathematics: A Computer Oriented Approach”, Tata McGraw-Hill, 2008.
- J. Kleinberg, “Algorithm Design”, Pearson India Education Services Pvt Ltd, 2014.
- K. Rosen, “Discrete Mathematics and Its Applications with Combinatorics and Graph Theory”, McGraw-Hill, 2012.
- R. Diestel, “Graph Theory”, Springer, 2017.
- J.A. Bondy, “Graph Theory with Applications”, Elsevier, 1976.
Abstract Views: 75
PDF Views: 2