CCTP, Graph Coloring Algorithms - Soft Computing Solutions

Graph coloring problem is NP-complete. It is polynomially reducible to classical and practical university timetabling problem. College course timetabling problem (CCTP) is a parallel instance of University course timetabling problem (UCTP). Obviously, heuristic and approximate algorithms are only ammunitions for solution of search problems. Soft computing approaches namely GA & ACO are particularly suitable to attack CCTP problems. We have seen that, in general timetabling problems need two criteria, compactness & balancing, that are obtainable by GA & ACO approaches. While it is observed that duo processor architecture based computers are readily available in the market, these approaches need cultivations afresh. In this paper we have initiated the process and hope for better culmination.