A very primitive version of Gotlieb’s timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multicommodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases.
No takes yet. Share an insight, caveat, or question.
Even et al. (1976) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: