An existential problem of a weight-controlled subset and its application to school timetable construction

DOI10.1016/0012-365X(88)90210-5zbMath0664.90076MaRDI QIDQ1115806

Fumio Kitagawa, Hideto Ikeda

Publication date: 1988

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph coloringnetwork flowschool timetable

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (17)

Equitable distinguishing chromatic number ⋮ Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs ⋮ HORES: A timetabling system for Spanish secondary schools ⋮ Equitable colorings of Kronecker products of graphs ⋮ The mutual exclusion scheduling problem for permutation and comparability graphs. ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ The equitable vertex arboricity of complete tripartite graphs ⋮ An XML format for benchmarks in high school timetabling ⋮ On the equitable vertex arboricity of graphs ⋮ On the equitable vertex arboricity of complete tripartite graphs ⋮ Equitable list coloring of planar graphs without 4- and 6-cycles ⋮ Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs ⋮ Equitable defective coloring of sparse planar graphs ⋮ Equitable colorings of Cartesian products of graphs ⋮ Distribution requirements and compactness constraints in school timetabling ⋮ Equitable colorings of bounded treewidth graphs ⋮ On equitable \(\Delta\)-coloring of graphs with low average degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On claw-decomposition of complete graphs and complete bigraphs
• A class of counterexamples on permanents
• A graph formulation of a school scheduling algorithm
• Graph coloring conditions for the existence of solutions to the timetable problem
• The application of a digital computer to the construction of timetables
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• A system for computing university examination timetables
• Matrix reduction using the Hungarian method for the generation of school timetables
• Techniques for Producing School Timetables on a Computer and their Application to other Scheduling Problems
• Tests on a computer method for constructing school timetables
• The preparation of examination time-tables using a small-store computer

This page was built for publication: An existential problem of a weight-controlled subset and its application to school timetable construction