Timetable Scheduling using Graph Coloring

	International Journal of P2P Network Trends and Technology (IJPTT)
	© 2011 by IJPTT Journal
	Volume-1 Issue-2
	Year of Publication : 2011
	Authors : Dr Cauvery N K

Citation

Dr Cauvery N K.T."Timetable Scheduling using Graph Coloring". International Journal of P2P Network Trends and Technology (IJPTT), V1(2):24-29  Sep - Oct 2011, ISSN:2249-2615, www.ijpttjournal.org. Published by Seventh Sense Research Group.

Abstract

which are polynomial bounded functions of input size. Therefore there is much interest in heuristic algorithms which can find near optimal solutions within reasonable running time. One of the most studied NP-hard problems is the “graph coloring problem”. Graph coloring has numerous applications in scheduling and other practical problem; “timetabling” is one of them. One of the heuristic approaches to solve graph coloring is “Ant algorithm” [1].

References

[1] SangHyuck Ahn, SeungGwan Lee, TaeChoong Chung, “Modified Ant Colony System for Coloring Graphs”, ICICS-FCM 2003 15-18 December 2003. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=12 92787
[2] Spyros Kazarlis, Vassilios Petridis and Pavlina Fragkou, “Solving University Timetabling Problems Using Advanced Genetic Algorithms”, International Journal, Vol. 4.2009, p no. 260-279.
[3] Ehsan Salari and Kourosh Eshghi,“An ACO Algorithm for the Graph Coloring Problem”, International Journal Contemp. Math. Sciences, Vol. 3, 2008, no. 6, 293 – 304.
[4] Malika Bessedik, Rafik Laib, Aissa Boulmerka et Habiba Drias, “Ant Colony System for Graph Coloring Problem”. J. Op. Res. Society, pp. 290-300 (2004)
[5] D. Costa and Hertz A. “Ant can colour graphs”, J. Op. Res. Society, pp. 295-305 (1997)
[6] E.K.Burke, D.G.Elliman, R.Weare, “A University Timetabling System based on Graph Colouring and Constraint Manipulation”.
[8] Dorigo M, Maniezzo V, Colorni A, “The ant system:Optimization by a colony of cooperation agents”,IEEE Transaction of Systems, Man and Cybernetics-Part B, vol 26, no.2 pp. 29-41(1996).
[9] Malika Bessedik, Rafik Laib,“Ant Colony System for Graph Coloring Problem”, International Conference on Computational Intelligence for Modeling, 2005.

Keywords

Graph coloring, Ant colony optimization, Pheremone trails