@article{ART001986518},
author={Sang-Un, Lee},
title={Chromatic Number Algorithm for Exam Scheduling Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={4},
pages={111-117}
TY - JOUR
AU - Sang-Un, Lee
TI - Chromatic Number Algorithm for Exam Scheduling Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 4
PB - The Korean Society Of Computer And Information
SP - 111
EP - 117
SN - 1598-849X
AB - The exam scheduling problem has been classified as nondeterministic polynomial time-complete (NPcomplete) problem because of the polynomial time algorithm to obtain the exact solution has been unknown yet. Guéret et al. tries to obtain the solution using linear programming with O(m4) time complexity for this problem. On the other hand, this paper suggests chromatic number algorithm with O(m) time complexity.
The proposed algorithm converts the original data to incompatibility matrix for modules and graph firstly.
Then, this algorithm packs the minimum degree vertex (module) and not adjacent vertex to this vertex into the bin Bi with color Ci in order to exam within minimum time period and meet the incompatibility constraints. As a result of experiments, this algorithm reduces the O(m4) of linear programming to O(m) time complexity for exam scheduling problem, and gets the same solution with linear programming.
KW - Incompatibility;Bin packing;NP-complete;Divide-and-conquer;Chromatic number
DO -
UR -
ER -
Sang-Un, Lee. (2015). Chromatic Number Algorithm for Exam Scheduling Problem. Journal of The Korea Society of Computer and Information, 20(4), 111-117.
Sang-Un, Lee. 2015, "Chromatic Number Algorithm for Exam Scheduling Problem", Journal of The Korea Society of Computer and Information, vol.20, no.4 pp.111-117.
Sang-Un, Lee "Chromatic Number Algorithm for Exam Scheduling Problem" Journal of The Korea Society of Computer and Information 20.4 pp.111-117 (2015) : 111.
Sang-Un, Lee. Chromatic Number Algorithm for Exam Scheduling Problem. 2015; 20(4), 111-117.
Sang-Un, Lee. "Chromatic Number Algorithm for Exam Scheduling Problem" Journal of The Korea Society of Computer and Information 20, no.4 (2015) : 111-117.
Sang-Un, Lee. Chromatic Number Algorithm for Exam Scheduling Problem. Journal of The Korea Society of Computer and Information, 20(4), 111-117.
Sang-Un, Lee. Chromatic Number Algorithm for Exam Scheduling Problem. Journal of The Korea Society of Computer and Information. 2015; 20(4) 111-117.
Sang-Un, Lee. Chromatic Number Algorithm for Exam Scheduling Problem. 2015; 20(4), 111-117.
Sang-Un, Lee. "Chromatic Number Algorithm for Exam Scheduling Problem" Journal of The Korea Society of Computer and Information 20, no.4 (2015) : 111-117.
