{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T04:58:44Z","timestamp":1768366724196,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10479-019-03382-0","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T20:48:43Z","timestamp":1572036523000},"page":"405-423","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Decomposition of university course timetabling"],"prefix":"10.1007","volume":"302","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0324-9640","authenticated-orcid":false,"given":"Britta","family":"Herres","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3371-6983","authenticated-orcid":false,"given":"Heinz","family":"Schmitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"issue":"3","key":"3382_CR1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/S0377-2217(01)00342-3","volume":"143","author":"A Asratian","year":"2002","unstructured":"Asratian, A., & de Werra, D. (2002). A generalized class-teacher model for some timetabling problems. European Journal of Operational Research, 143(3), 531\u2013542.","journal-title":"European Journal of Operational Research"},{"key":"3382_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.cie.2014.11.010","volume":"86","author":"H Babaei","year":"2015","unstructured":"Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers and Industrial Engineering, 86, 43\u201359.","journal-title":"Computers and Industrial Engineering"},{"key":"3382_CR3","unstructured":"Chen, H. (2006). Logic column 17: A rendezvous of logic, complexity, and algebra. CoRR abs\/cs\/0611018, arXiv:cs\/0611018"},{"issue":"1","key":"3382_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R Cole","year":"2001","unstructured":"Cole, R., Ost, K., & Schirra, S. (2001). Edge-coloring bipartite multigraphs in O (E log D) time. Combinatorica, 21(1), 5\u201312.","journal-title":"Combinatorica"},{"key":"3382_CR5","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-61794-9_66","volume-title":"Practice and theory of automated timetabling","author":"TB Cooper","year":"1996","unstructured":"Cooper, T. B., & Kingston, J. H. (1996). The complexity of timetable construction problems. In E. Burke & P. Ross (Eds.), Practice and theory of automated timetabling (pp. 281\u2013295). Heidelberg: Springer."},{"key":"3382_CR6","unstructured":"Csima, J. (1965). Investigations on a time-table problem. Ph.D. thesis, School of Graduate Studies, University of Toronto."},{"issue":"1","key":"3382_CR7","first-page":"12","volume":"9","author":"D de Werra","year":"1971","unstructured":"de Werra, D. (1971). Construction of school timetables by flow methods. INFOR Journal, 9(1), 12\u201322.","journal-title":"INFOR Journal"},{"key":"3382_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-45157-0_1","volume-title":"Practice and theory of automated timetabling IV","author":"D de Werra","year":"2003","unstructured":"de Werra, D. (2003). Constraints of availability in timetabling and scheduling. In E. Burke & P. De Causmaecker (Eds.), Practice and theory of automated timetabling IV (pp. 3\u201323). Heidelberg: Springer."},{"issue":"3","key":"3382_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10951-015-0424-2","volume":"19","author":"M Dostert","year":"2016","unstructured":"Dostert, M., Politz, A., & Schmitz, H. (2016). A complexity analysis and an algorithmic approach to student sectioning in existing timetables. Journal of Scheduling, 19(3), 285\u2013293.","journal-title":"Journal of Scheduling"},{"key":"3382_CR10","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A., & Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, SFCS \u201975, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1975.21"},{"key":"3382_CR11","first-page":"243","volume-title":"Maximal flow through a network","author":"LR Ford","year":"1987","unstructured":"Ford, L. R., & Fulkerson, D. R. (1987). Maximal flow through a network (pp. 243\u2013248). Boston: Birkh\u00e4user Boston."},{"key":"3382_CR12","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman and Co."},{"key":"3382_CR13","unstructured":"Gaspero, L.D., Mccollum, B., & Schaerf, A. (2007). The second international timetabling competition (itc-2007): Curriculum-based course timetabling (track 3. Tech. rep."},{"key":"3382_CR14","unstructured":"Gotlieb, C.C. (1962). The Construction of class-teacher time-tables. In: IFIP Congress, pp 73\u201377"},{"issue":"4","key":"3382_CR15","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I. (1981). The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4), 718\u2013720.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"3382_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J. E., & Karp, R. M. (1973). An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225\u2013231.","journal-title":"SIAM Journal on Computing"},{"key":"3382_CR17","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85\u2013103). Boston: Springer."},{"issue":"1","key":"3382_CR18","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10479-012-1160-z","volume":"218","author":"JH Kingston","year":"2014","unstructured":"Kingston, J. H. (2014). Timetable construction: the algorithms and complexity perspective. Annals of Operations Research, 218(1), 249\u2013259.","journal-title":"Annals of Operations Research"},{"key":"3382_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/11593577_7","volume-title":"Practice and theory of automated timetabling V","author":"P Kostuch","year":"2005","unstructured":"Kostuch, P. (2005). The university course timetabling problem with a three-phase approach. In E. Burke & M. Trick (Eds.), Practice and theory of automated timetabling V (pp. 109\u2013125). Heidelberg: Springer."},{"key":"3382_CR20","unstructured":"Kristiansen, S., & Stidsen, T. (2013). A comprehensive study of educational timetabling\u2014a survey. Report 8.2013, Department of Management Engineering, Technical University of Denmark"},{"issue":"1","key":"3382_CR21","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10479-010-0700-7","volume":"194","author":"G Lach","year":"2012","unstructured":"Lach, G., & L\u00fcbbecke, M. E. (2012). Curriculum based course timetabling: new solutions to Udine benchmark instances. Annals of Operations Research, 194(1), 255\u2013272.","journal-title":"Annals of Operations Research"},{"key":"3382_CR22","unstructured":"Lewis, R., Paechter, B., & Mccollum, B. (2007). Post enrolment based course timetabling: A description of the problem model used for track two of the second international timetabling competition. Cardiff University, Cardiff Business School, Accounting and Finance Section, Cardiff Accounting and Finance Working Papers"},{"issue":"4","key":"3382_CR23","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20085","volume":"49","author":"D Marx","year":"2005","unstructured":"Marx, D. (2005). NP-completeness of list coloring and precoloring extension on the edges of planar graphs. Journal of Graph Theory, 49(4), 313\u2013324.","journal-title":"Journal of Graph Theory"},{"key":"3382_CR24","unstructured":"McCollum, B. (2006). University Timetabling: Bridging the Gap between Research and Practice. In: in Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Springer, pp. 15\u201335."},{"key":"3382_CR25","unstructured":"M\u00fcller, T., Rudova, H., & M\u00fcllerova, Z. (2018). University course timetabling and international timetabling competition 2019. In: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling (PATAT 2018), Vienna, Austria, pp. 5 \u2013 31."},{"key":"3382_CR26","unstructured":"Paechter, B., Gambardella, L.M., & Rossi-Doria, O. (2002). The first international timetabling competition. URL http:\/\/www.idsia.ch\/Files\/ttcomp2002\/(2002)"},{"issue":"1","key":"3382_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0166-218X(80)90055-4","volume":"2","author":"DA Plaisted","year":"1980","unstructured":"Plaisted, D. A., & Zaks, S. (1980). An NP-complete matching problem. Discrete Applied Mathematics, 2(1), 65\u201372.","journal-title":"Discrete Applied Mathematics"},{"key":"3382_CR28","unstructured":"Rudova, H. (2015). University course timetabling\u2014from theory to practice. In: Multidisciplinary International Scheduling Conference (MISTA 2015) (Talk), Prague, Czech Republic, URL https:\/\/www.fi.muni.cz\/~hanka\/publ\/mista15.pdf"},{"key":"3382_CR29","doi-asserted-by":"publisher","unstructured":"Schaefer, T.J. (1978). The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pp. 216\u2013226, https:\/\/doi.org\/10.1145\/800133.804350","DOI":"10.1145\/800133.804350"},{"issue":"1","key":"3382_CR30","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10479-017-2621-1","volume":"275","author":"D Schindl","year":"2019","unstructured":"Schindl, D. (2019). Optimal student sectioning on mandatory courses with various sections numbers. Annals of Operations Research, 275(1), 209\u2013221. https:\/\/doi.org\/10.1007\/s10479-017-2621-1.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"3382_CR31","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322093","volume":"25","author":"SL Tanimoto","year":"1978","unstructured":"Tanimoto, S. L., Itai, A., & Rodeh, M. (1978). Some matching problems for bipartite graphs. Journal of the ACM, 25(4), 517\u2013525.","journal-title":"Journal of the ACM"},{"key":"3382_CR32","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/3-540-44629-X_2","volume-title":"Practice and theory of automated timetabling III","author":"HMM ten Eikelder","year":"2001","unstructured":"ten Eikelder, H. M. M., & Willemen, R. J. (2001). Some complexity aspects of secondary school timetabling problems. In E. Burke & W. Erben (Eds.), Practice and theory of automated timetabling III (pp. 18\u201327). Heidelberg: Springer."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03382-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-019-03382-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03382-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T16:15:34Z","timestamp":1623946534000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-019-03382-0"}},"subtitle":["A systematic study of subproblems and their complexities"],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["3382"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03382-0","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"25 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}