Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths

DOI10.1016/0377-2217(91)90254-SzbMath0747.90098MaRDI QIDQ1179200

Jan A. M. Schreuder, Mirjana Čangalović

Publication date: 26 June 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

timetablingexact algorithmvertex-colouringinterval \(k\)-colouringinterval chromatic number

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

On the use of some known methods for \(T\)-colorings of graphs, Comparison of metaheuristic algorithms for examination timetabling problem, School timetabling for quality student and teacher schedules, Iterative coloring extension of a maximum clique, Scheduling independent tasks with multiple modes, On a reduction of the interval coloring problem to a series of bandwidth coloring problems, CHECKCOL: improved local search for graph coloring, Modelling and solving an acyclic multi-period timetabling problem, Finding a feasible course schedule using Tabu search, Implementation of a university course and examination timetabling system, About equivalent interval colorings of weighted graphs, Hybrid heuristics for examination timetabling problem, Comparability graph augmentation for some multiprocessor scheduling problems, Distribution requirements and compactness constraints in school timetabling, The course scheduling problem at Lufthansa technical training, An integer program and a hybrid genetic algorithm for the university timetabling problem

Cites Work

• Unnamed Item
• Unnamed Item
• An introduction to timetabling
• Chromatic optimisation: Limitations, objectives, uses, references
• Combinatorial Optimization Problems with Soft and Hard Requirements
• Consecutive colorings of graphs
• Simulated annealing: An introduction
• Algorithms for finding in the lump both bounds of the chromatic number of a graph
• New methods to color the vertices of a graph
• Approximate Colouring Algorithms for Composite Graphs
• Chromatic Scheduling and the Chromatic Number Problem