Weighted graphs and university course timetabling

A weighted graph is used to model the problem of scheduling university courses minimizing conflict. A variety of vertex section criteria are introduced, and are used in a heuristic algorithm for finding approximate solutions in the form of least-cost k-colorings. The trade-off between these approximate algorithms and exact integer programming methods is discussed, and computational results are presented.