SIAM Journal on Computing · 1976 · 1.1K citations · 7 references
Mathematical ProgrammingComputational Complexity TheoryEngineeringComputational ComplexityDiscrete OptimizationTimetable ProblemP Versus Np ProblemDiscrete MathematicsCombinatorial OptimizationMeeting FunctionCombinatorial ProblemComputer ScienceInteger ProgrammingScheduling AnalysisMulticommodity Flow ProblemsScheduling ProblemPrimitive VersionTime ComplexityComputational Problem
A very primitive version of Gotlieb’s timetable problem is shown to be NP‑complete, implying that all common timetable problems are NP‑complete. The study presents a polynomial‑time algorithm for binary‑teacher timetabling, proves existence of a meeting function when teachers and classes have no time constraints, and shows that the multicommodity integral flow problem is NP‑complete even with two commodities in both directed and undirected graphs.
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.
7
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
Computational Complexity Theory, Engineering, Constructive Logic +18
On the Computational Complexity of Combinatorial Problems
Richard M. Karp · Networks · 1975 · 706 citations
Computational Graph Theory, Engineering, Network Analysis +21
T. C. Hu · Operations Research · 1963 · 390 citations