Decomposition of university course timetabling. A systematic study of subproblems and their complexities

DOI10.1007/s10479-019-03382-0zbMath1476.90118OpenAlexW2981995148MaRDI QIDQ2241151

Heinz Schmitz, Britta Herres

Publication date: 8 November 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-019-03382-0

zbMATH Keywords

complexity analysisdecomposition approachbipartite assignment problemsfoundations of university course timetabling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complexity analysis and an algorithmic approach to student sectioning in existing timetables
• Timetable construction: the algorithms and complexity perspective
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• An NP-complete matching problem
• Optimal student sectioning on mandatory courses with various sections numbers
• Curriculum based course timetabling: new solutions to Udine benchmark instances
• A generalized class-teacher model for some timetabling problems
• The NP-Completeness of Edge-Coloring
• Some Matching Problems for Bipartite Graphs
• Reducibility among Combinatorial Problems
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• The complexity of satisfiability problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Decomposition of university course timetabling. A systematic study of subproblems and their complexities