Extended Clique Initialisation in Examination Timetabling

Many examination timetabling procedures employ a phased approach in which the first phase is often the allocation of a large set of mutually conflicting examinations which form a clique in the associated problem graph. The usual practice is to identify a single maximum clique, often quite arbitraril...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 2001-05, Vol.52 (5), p.538-544
Main Authors: Carter, M. W., Johnson, D. G.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Graph theory
Graphs
Integers
Operational research and scientific management
Operational research. Management science
Operations research
Pruning
Studies
Theoretical Papers
Vertices
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many examination timetabling procedures employ a phased approach in which the first phase is often the allocation of a large set of mutually conflicting examinations which form a clique in the associated problem graph. The usual practice is to identify a single maximum clique, often quite arbitrarily, in this first phase. We show that in typical examination timetabling problems, unlike random graphs, there are often many alternative maximum cliques, and even larger dense subsets of nodes that are almost cliques. A number of methods are proposed for extending the scope of the clique initialisation to include a larger subset of examinations by considering sub-maximum cliques and/or quasi-cliques.
ISSN:0160-5682
1476-9360
0160-5682
DOI:10.1038/sj.jors.2601115