A Study of Weighted Graph Coloring Algorithm for Timetabling Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 12, pp. 3151-3157, Dec. 1998
10.3745/KIPSTE.1998.5.12.3151,   PDF Download:

Abstract

Timetabling problems have often been formulated as coloring problems in graph. The lectures are represented by vertices, and edges join those paris of vertices whose corresponding lectures can not be assigned in same period. Such formulation, however, imposes a significant limitation on the flexibility of the model of timetabling-problem, since it is not possible to incorporate any of the consecutive lecture constraints that frequently occur in real problem. Therefore, the concept of weighted graph coloring have been introduced to overcome this limitation. In this case, the each node has a weight number representing the length of a lecture. Many researches have been dealt with this problem but they have difficulties to overcome exponentially increased search time and to guarantee good solution. We propose a new weighted-graph-coloring algorithm to solve it.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. M. Jae, A. J. II, C. T. Choong, "A Study of Weighted Graph Coloring Algorithm for Timetabling Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 12, pp. 3151-3157, 1998. DOI: 10.3745/KIPSTE.1998.5.12.3151.

[ACM Style]
Kim Myung Jae, Ahn Jong II, and Chung Tae Choong. 1998. A Study of Weighted Graph Coloring Algorithm for Timetabling Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 12, (1998), 3151-3157. DOI: 10.3745/KIPSTE.1998.5.12.3151.