On the Complexity of Timetable and Multicommodity Flow Problems

1976/12/01 by Shimon Even, Alon Itai, Adi Shamir · 12 citations
Decision Sciences · Engineering · Mathematics · #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods #Scheduling and Optimization Algorithms #Mathematics #Multi-commodity flow problem #Time complexity #Function (biology) #Flow (mathematics) #Combinatorics #Binary number #Computational complexity theory #NP-complete #Discrete mathematics #Mathematical optimization #Flow network #Algorithm #Arithmetic

paper · doi:10.1137/0205048

openalex publication_date 1976/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/25

Abstract

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.

Citations

• On Representatives of Subsets
• Multi-Commodity Network Flows
• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Cited by

• La competencia y la función de fabricación
• A linear-time algorithm for testing the truth of certain quantified boolean formulas
• A packing problem with applications to lettering of maps
• Bisplit graphs
• A polynomial time solution for labeling a rectilinear map
• Advanced Many-Valued Logics
• A practical map labeling algorithm
• Single bend wiring
• Complexity of Many-valued Logics
• Network flow and 2-satisfiability
• Mick gets some (the odds are on his side) (satisfiability)
• 2-satisfiability [wikipedia]