{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T07:52:52Z","timestamp":1774770772830,"version":"3.50.1"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,3,30]],"date-time":"2010-03-30T00:00:00Z","timestamp":1269907200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s10479-010-0716-z","type":"journal-article","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T16:57:24Z","timestamp":1269881844000},"page":"105-130","source":"Crossref","is-referenced-by-count":62,"title":["A supernodal formulation of vertex colouring with\u00a0applications in course timetabling"],"prefix":"10.1007","volume":"179","author":[{"given":"Edmund K.","family":"Burke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Mare\u010dek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew J.","family":"Parkes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hana","family":"Rudov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,3,30]]},"reference":[{"key":"716_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"K. I. Aardal","year":"2007","unstructured":"Aardal, K. I., Hoesel, S. P. M., van Koster, A. M. C. A., & Mannino, C. (2007). Models and solution techniques for frequency assignment problems. Annals of Operation Research, 153, 79\u2013129.","journal-title":"Annals of Operation Research"},{"issue":"3","key":"716_CR2","first-page":"1333","volume":"163","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., & Naor, A. (2005). The two possible values of the chromatic number of a random graph. Annals of Mathematics, 163(3), 1333\u20131349.","journal-title":"Annals of Mathematics"},{"key":"716_CR3","unstructured":"Achterberg, T. (2007). Constraint integer programming. Unpublished doctoral dissertation, Berlin."},{"issue":"3","key":"716_CR4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.ipl.2005.01.009","volume":"94","author":"G. Appa","year":"2005","unstructured":"Appa, G., Magos, D., & Mourtos, I. (2005). On the system of two all_different predicates. Information Processing Letters, 94(3), 99\u2013105.","journal-title":"Information Processing Letters"},{"issue":"6","key":"716_CR5","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s10951-005-4780-1","volume":"8","author":"P. Avella","year":"2005","unstructured":"Avella, P., & Vasil\u2019ev, I. (2005). A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8(6), 497\u2013514.","journal-title":"Journal of Scheduling"},{"key":"716_CR6","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0020-0190(99)00120-9","volume":"72","author":"V. C. Barbosa","year":"1999","unstructured":"Barbosa, V. C., & Szwarcfiter, J. L. (1999). Generating all the acyclic orientations of an undirected graph. Information Processing Letters, 72, 71\u201374.","journal-title":"Information Processing Letters"},{"issue":"1","key":"716_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/B:JOCO.0000021937.26468.b2","volume":"8","author":"V. C. Barbosa","year":"2004","unstructured":"Barbosa, V. C., Assis, C. A. G., & Nascimento, J. O. do. (2004). Two novel evolutionary formulations of the graph coloring problem. Journal of Combinatorial Optimization, 8(1), 41\u201363.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"716_CR8","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1057\/palgrave.jors.2602523","volume":"60","author":"C. B. Beyrouthy","year":"2008","unstructured":"Beyrouthy, C. B., Burke, E. K., Silva, D. L., McCollum, B., McMullan, P., & Parkes, A. J. (2008). Towards improving the utilisation of university teaching space. Journal of the Operational Research Society, 60(1), 130\u2013143.","journal-title":"Journal of the Operational Research Society"},{"key":"716_CR9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B. (2001). Random graphs. Cambridge: Cambridge University Press."},{"issue":"2","key":"716_CR10","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/S0377-2217(02)00069-3","volume":"140","author":"E. K. Burke","year":"2002","unstructured":"Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266\u2013280.","journal-title":"European Journal of Operational Research"},{"key":"716_CR11","first-page":"445","volume-title":"Handbook of graph theory","author":"E. K. Burke","year":"2004","unstructured":"Burke, E. K., Werra, D., & Kingston, J. H. (2004). Applications to timetabling. In J. L. Gross & J. Yellen (Eds.), Handbook of graph theory (pp.\u00a0445\u2013474). Boca Raton: CRC Press."},{"key":"716_CR12","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/978-3-540-77903-2_63","volume-title":"Operations research proceedings 2007","author":"E. K. Burke","year":"2008","unstructured":"Burke, E. K., Mare\u010dek, J., Parkes, A. J., & Rudov\u00e1, H. (2008). Penalising patterns in timetables: novel integer programming formulations. In S. Nickel & J. Kalcsics (Eds.), Operations research proceedings 2007 (pp.\u00a0409\u2013414). Berlin: Springer."},{"issue":"4","key":"716_CR13","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.ipl.2003.11.005","volume":"89","author":"M. Camp\u00ealo","year":"2003","unstructured":"Camp\u00ealo, M., Corr\u00eaa, R. C., & Frota, Y. (2003). Cliques, holes and the vertex coloring polytope. Information Processing Letters, 89(4), 159\u2013164.","journal-title":"Information Processing Letters"},{"issue":"7","key":"716_CR14","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/j.dam.2007.05.058","volume":"156","author":"M. Camp\u00ealo","year":"2008","unstructured":"Camp\u00ealo, M., Campos, V. A., & Corr\u00eaa, R. C. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156(7), 1097\u20131111.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"716_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1590\/S0101-74382009000100009","volume":"29","author":"M. Camp\u00ealo","year":"2009","unstructured":"Camp\u00ealo, M., Campos, V. A., & Corr\u00eaa, R. C. (2009). Um algoritmo de\u00a0planos-de-corte para o n\u00famero crom\u00e1tico fracion\u00e1rio de\u00a0um grafo. Pesquisa Operacional, 29(1), 179\u2013193.","journal-title":"Pesquisa Operacional"},{"issue":"1\u20133","key":"716_CR16","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0166-218X(98)00046-8","volume":"87","author":"A. Caprara","year":"1998","unstructured":"Caprara, A. (1998). Properties of some ilp formulations of a class of partitioning problems. Discrete Applied Mathematics, 87(1\u20133), 11\u201323.","journal-title":"Discrete Applied Mathematics"},{"key":"716_CR17","series-title":"LNCS","first-page":"3","volume-title":"Practice and theory of automated timetabling","author":"M. W. Carter","year":"1997","unstructured":"Carter, M. W., & Laporte, G. (1997). Recent developments in practical course timetabling. In E. K. Burke & M. W. Carter (Eds.), LNCS: Vol.\u00a01408. Practice and theory of automated timetabling (pp.\u00a03\u201319). Berlin: Springer."},{"key":"716_CR18","unstructured":"Catanzaro, D., Godi, A., & Labb\u00e9, M. (2008). A class representative model for pure parsimony haplotyping (Tech. Rep. Nos. Dated October 29, 2008). Bruxelles, Belgium: Universit\u00e9 Libre de Bruxelles."},{"issue":"1","key":"716_CR19","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (2006). The strong perfect graph theorem. Annals of Mathematics, 164(1), 51\u2013229.","journal-title":"Annals of Mathematics"},{"key":"716_CR20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1023\/A:1021315911306","volume":"116","author":"P. Coll","year":"2002","unstructured":"Coll, P., Marenco, J., M\u00e9ndez-D\u00edaz, I., & Zabala, P. (2002). Facets of the graph coloring polytope. Annals of Operation Research, 116, 79\u201390.","journal-title":"Annals of Operation Research"},{"key":"716_CR21","unstructured":"Crescenzi, P., Kann, V., Halld\u00f3rsson, M., Karpinski, M., & Woeginger, G. (2005). A compendium of NP optimization problems (Available on-line)."},{"issue":"3","key":"716_CR22","doi-asserted-by":"crossref","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","volume":"32","author":"W. H. Cunningham","year":"1980","unstructured":"Cunningham, W. H., & Edmonds, J. (1980). A combinatorial decomposition theory. Canadian Journal of Mathematics, 32(3), 734\u2013765.","journal-title":"Canadian Journal of Mathematics"},{"issue":"3","key":"716_CR23","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/356044.356047","volume":"9","author":"I. S. Duff","year":"1983","unstructured":"Duff, I. S., & Reid, J. K. (1983). The multifrontal solution of indefinite sparse symmetric linear. ACM Transactions on Mathematical Software, 9(3), 302\u2013325.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"716_CR24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/B978-0-12-100560-3.50009-3","volume-title":"Elliptic problem solvers, II","author":"S. C. Eisenstat","year":"1984","unstructured":"Eisenstat, S. C., Elman, H. C., Schultz, M. H., & Sherman, A. H. (1984). The (new) yale sparse matrix package. In Elliptic problem solvers, II (Monterey, Calif., 1983), (pp.\u00a045\u201352). San Diego: Academic Press."},{"issue":"2","key":"716_CR25","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., & Kilian, J. (1998). Zero knowledge and the chromatic number. Journal of Computer and System Science, 57(2), 187\u2013199.","journal-title":"Journal of Computer and System Science"},{"issue":"9","key":"716_CR26","doi-asserted-by":"crossref","first-page":"2547","DOI":"10.1016\/j.cor.2005.07.028","volume":"33","author":"P. Galinier","year":"2006","unstructured":"Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33(9), 2547\u20132562.","journal-title":"Computers & Operations Research"},{"key":"716_CR27","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T. (1967). Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungar, 18, 25\u201366.","journal-title":"Acta Mathematica Academiae Scientiarum Hungar"},{"key":"716_CR28","first-page":"115","volume-title":"Theory of graphs","author":"T. Gallai","year":"1968","unstructured":"Gallai, T. (1968). On directed paths and circuits. In P. Erd\u00f6s & G. Katobna (Eds.), Theory of graphs (pp.\u00a0115\u2013118). San Diego: Academic Press."},{"issue":"1","key":"716_CR29","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M. R. Garey","year":"1976","unstructured":"Garey, M. R., & Johnson, D. S. (1976). The complexity of near-optimal graph coloring. Journal of the ACM, 23(1), 43\u201349.","journal-title":"Journal of the ACM"},{"key":"716_CR30","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-540-45157-0_17","volume-title":"Practice and theory of automated timetabling","author":"L. D. Gaspero","year":"2003","unstructured":"Gaspero, L. D., & Schaerf, A. (2003). Multi neighborhood local search with application to the course timetabling problem. In E. K. Burke & P. D. Causmaecker (Eds.), LNCS: Vol.\u00a02740. Practice and theory of automated timetabling (pp.\u00a0262\u2013275). Berlin: Springer."},{"issue":"1","key":"716_CR31","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10852-005-9032-z","volume":"5","author":"L. D. Gaspero","year":"2006","unstructured":"Gaspero, L. D., & Schaerf, A. (2006). Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modelling and Algorithms, 5(1), 65\u201389.","journal-title":"Journal of Mathematical Modelling and Algorithms"},{"issue":"4","key":"716_CR32","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/S0036144504444711","volume":"47","author":"A. H. Gebremedhin","year":"2005","unstructured":"Gebremedhin, A. H., Manne, F., & Pothen, A. (2005). What color is your Jacobian? Graph coloring for computing derivatives. SIAM Review, 47(4), 629\u2013705.","journal-title":"SIAM Review"},{"issue":"1","key":"716_CR33","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/0715006","volume":"15","author":"A. George","year":"1978","unstructured":"George, A., & McIntyre, D. R. (1978). On the application of the minimum degree algorithm to finite element systems. SIAM Journal of Numerical Analysis, 15(1), 90\u2013112.","journal-title":"SIAM Journal of Numerical Analysis"},{"issue":"3","key":"716_CR34","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02253207","volume":"18","author":"M. C. Golumbic","year":"1977","unstructured":"Golumbic, M. C. (1977). The complexity of comparability graph recognition and coloring. Computing, 18(3), 199\u2013208.","journal-title":"Computing"},{"key":"716_CR35","volume-title":"Handbook of graph theory","author":"J. L. Gross","year":"2004","unstructured":"Gross, J. L., & Yellen, J. (2004). Handbook of graph theory. Boca Raton: CRC Press."},{"issue":"3","key":"716_CR36","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0166-218X(79)90043-X","volume":"1","author":"M. Habib","year":"1979","unstructured":"Habib, M., & Maurer, M. C. (1979). On the X-join decomposition for undirected graphs. Discrete Applied Mathematics, 1(3), 201\u2013207.","journal-title":"Discrete Applied Mathematics"},{"key":"716_CR37","unstructured":"Hansen, P., Labb\u00e9, M., & Schindl, D. (2005). Set covering and packing formulations of graph coloring: algorithms and first polyhedral results (Tech. Rep. No. G-2005-76). Montreal, Canada: GERAD."},{"key":"716_CR38","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, Workshop","author":"D. J. Johnson","year":"1996","unstructured":"Johnson, D. J., & Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, Workshop, October 11\u201313, 1993. Providence: American Mathematical Society."},{"key":"716_CR39","unstructured":"Kaibel, V., & Margot, F. (2007). Personal communication at MIP Workshop 2007 in Montreal, Canada."},{"issue":"1","key":"716_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-006-0081-5","volume":"114","author":"V. Kaibel","year":"2008","unstructured":"Kaibel, V., & Pfetsch, M. (2008). Packing and partitioning orbitopes. Mathematical Programming, 114(1), 1\u201336. doi: 10.1007\/s10107-006-0081-5 .","journal-title":"Mathematical Programming"},{"key":"716_CR41","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-540-72792-7_7","volume-title":"Integer programming and combinatorial optimization","author":"V. Kaibel","year":"2007","unstructured":"Kaibel, V., Peinhardt, M., & Pfetsch, M. E. (2007). Orbitopal fixing. In M. Fischetti & D. P. Williamson (Eds.), LNCS: Vol.\u00a04513. Integer programming and combinatorial optimization (pp.\u00a074\u201388). New York: Springer."},{"key":"716_CR42","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp.\u00a085\u2013103). New York: Plenum."},{"issue":"1","key":"716_CR43","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0305-0548(92)90059-E","volume":"19","author":"L. Kiaer","year":"1992","unstructured":"Kiaer, L., & Yellen, J. (1992). Weighted graphs and university course timetabling. Computers Operations Research, 19(1), 59\u201367.","journal-title":"Computers Operations Research"},{"key":"716_CR44","unstructured":"Koch, T. (2004). Rapid mathematical programming. Unpublished doctoral dissertation, Berlin (ZIB Technical Report TR-04-58)."},{"issue":"2","key":"716_CR45","doi-asserted-by":"crossref","first-page":"457","DOI":"10.2307\/2275541","volume":"62","author":"J. Kraj\u00ed\u010dek","year":"1997","unstructured":"Kraj\u00ed\u010dek, J. (1997). Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Journal of Symbolic Logic, 62(2), 457\u2013486.","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"716_CR46","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1023\/A:1014804110661","volume":"6","author":"J. Lee","year":"2002","unstructured":"Lee, J. (2002). All-different polytopes. Journal of Combinatorial Optimization, 6(3), 335\u2013352.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"716_CR47","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1287\/ijoc.1060.0178","volume":"19","author":"J. Lee","year":"2007","unstructured":"Lee, J., & Margot, F. (2007). On a binary-encoded ILP coloring formulation. INFORMS Journal of Computing, 19(3), 406\u2013415.","journal-title":"INFORMS Journal of Computing"},{"key":"716_CR48","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10107-002-0358-2","volume":"94","author":"F. Margot","year":"2002","unstructured":"Margot, F. (2002). Pruning by isomorphism in branch-and-cut. Mathematical Programming, 94, 71\u201390.","journal-title":"Mathematical Programming"},{"key":"716_CR49","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-003-0394-6","volume":"98","author":"F. Margot","year":"2003","unstructured":"Margot, F. (2003). Exploiting orbits in symmetric ILP. Mathematical Programming, 98, 3\u201331.","journal-title":"Mathematical Programming"},{"key":"716_CR50","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.disopt.2006.10.008","volume":"4","author":"F. Margot","year":"2007","unstructured":"Margot, F.: (2007). Symmetric ILP: Coloring and small integers. Discrete Optimization, 4, 40\u201362.","journal-title":"Discrete Optimization"},{"issue":"4","key":"716_CR51","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A. Mehrotra","year":"1996","unstructured":"Mehrotra, A., & Trick, M. A. (1996). A column generation approach for graph coloring. INFORMS Journal of Computing, 8(4), 344\u2013354.","journal-title":"INFORMS Journal of Computing"},{"key":"716_CR52","first-page":"2","volume":"156","author":"I. M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., & Zabala, P. (2008). A cutting plane algorithm for graph coloring. Discrete Applied Mathematics, 156, 2.","journal-title":"Discrete Applied Mathematics"},{"key":"716_CR53","first-page":"257","volume-title":"Algebraic and combinatorial methods in operations research","author":"R. H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R. H., & Radermacher, F. J. (1984). Substitution decomposition for discrete structures and connections with combinatorial optimization. In Algebraic and combinatorial methods in operations research (Vol.\u00a095, pp.\u00a0257\u2013355). Amsterdam: North-Holland."},{"issue":"1","key":"716_CR54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J. H. Muller","year":"1989","unstructured":"Muller, J. H., & Spinrad, J. (1989). Incremental modular decomposition. Journal of the ACM, 36(1), 1\u201319.","journal-title":"Journal of the ACM"},{"key":"716_CR55","series-title":"LNCS","first-page":"193","volume-title":"Practice and theory of automated timetabling","author":"K. Murray","year":"2007","unstructured":"Murray, K., M\u00fcller, T., & Rudov\u00e1, H. (2007). Modeling and solution of a complex university course timetabling problem. In E. K. Burke & H. Rudov\u00e1 (Eds.), LNCS: Vol.\u00a03867. Practice and theory of automated timetabling (pp.\u00a0193\u2013213). Berlin: Springer."},{"issue":"1","key":"716_CR56","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.ejc.2003.09.024","volume":"29","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., & Tardif, C. (2008). A dualistic approach to bounding the chromatic number of a graph. European Journal of Combinatorics, 29(1), 254\u2013260.","journal-title":"European Journal of Combinatorics"},{"key":"716_CR57","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/978-3-540-72792-7_9","volume-title":"Integer programming and combinatorial optimization","author":"J. Ostrowski","year":"2007","unstructured":"Ostrowski, J., Linderoth, J., Rossi, F., & Smriglio, S. (2007). Orbital branching. In M. Fischetti & D. P. Williamson (Eds.), LNCS: Vol.\u00a04513. Integer programming and combinatorial optimization (pp.\u00a0104\u2013118). New York: Springer."},{"key":"716_CR58","first-page":"1001","volume-title":"Handbook of scheduling: Algorithms, models, and performance analysis","author":"S. Petrovic","year":"2004","unstructured":"Petrovic, S., & Burke, E. K. (2004). University timetabling. In J. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis (pp.\u00a01001\u20131023). Boca Raton: CRC Press."},{"key":"716_CR59","series-title":"LNCS","first-page":"105","volume-title":"Theory and applications of satisfiability testing","author":"S. D. Prestwich","year":"2003","unstructured":"Prestwich, S. D. (2003). In E. Giunchiglia & A. Tacchella (Eds.), LNCS: Vol.\u00a02919. Theory and applications of satisfiability testing (pp.\u00a0105\u2013119). Berlin: Springer."},{"key":"716_CR60","first-page":"127","volume":"1","author":"B. Roy","year":"1967","unstructured":"Roy, B. (1967). Nombre chromatique et plus longs chemins d\u2019un graph. Revue AFIRO, 1, 127\u2013132.","journal-title":"Revue AFIRO"},{"key":"716_CR61","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/978-3-540-45157-0_21","volume-title":"Practice and theory of automated timetabling","author":"H. Rudov\u00e1","year":"2003","unstructured":"Rudov\u00e1, H., & Murray, K. (2003). University course timetabling with soft constraints. In E. K. Burke & P.\u00a0D.\u00a0Causmaecker (Eds.), LNCS: Vol.\u00a02740. Practice and theory of automated timetabling (pp.\u00a0310\u2013328). Berlin: Springer."},{"key":"716_CR62","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF01210984","volume":"76","author":"G. Sabidussi","year":"1961","unstructured":"Sabidussi, G. (1961). Graph derivatives. Mathematische Zeitschrift, 76, 385\u2013401.","journal-title":"Mathematische Zeitschrift"},{"issue":"2","key":"716_CR63","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1023\/A:1006576209967","volume":"13","author":"A. Schaerf","year":"1999","unstructured":"Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87\u2013127.","journal-title":"Artificial Intelligence Review"},{"key":"716_CR64","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1007\/s00291-006-0074-z","volume":"29","author":"K. Schimmelpfeng","year":"2007","unstructured":"Schimmelpfeng, K., & Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29, 783\u2013803.","journal-title":"OR Spectrum"},{"key":"716_CR65","unstructured":"Schindl, D. (2004). Some combinatorial optimization problems in graphs with applications in telecommunications and tomography. Unpublished doctoral dissertation, Lausanne."},{"key":"716_CR66","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-642-87617-2_13","volume-title":"New methods of thought and procedure","author":"L. Shapley","year":"1967","unstructured":"Shapley, L. (1967). On committees. In New methods of thought and procedure (pp.\u00a0246\u2013270). Berlin: Springer."},{"issue":"7","key":"716_CR67","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1109\/43.293941","volume":"13","author":"D. L. Springer","year":"1994","unstructured":"Springer, D. L., & Thomas, D. E. (1994). Exploiting the special structure of conflict and compatibility graphs in high-level synthesis. IEEE Transactions on CAD of Integrated Circuits and Systems, 13(7), 843\u2013856.","journal-title":"IEEE Transactions on CAD of Integrated Circuits and Systems"},{"key":"716_CR68","first-page":"758","volume":"147","author":"L. M. Vitaver","year":"1962","unstructured":"Vitaver, L. M. (1962). Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix. Doklady Akademii Nauk SSSR, 147, 758\u2013759.","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"3","key":"716_CR69","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0020-0190(03)00266-7","volume":"87","author":"D. Werra de","year":"2003","unstructured":"de Werra, D., & Hansen, P. (2003). Using stable sets to bound the chromatic number. Information Processing Letters, 87(3), 127\u2013131.","journal-title":"Information Processing Letters"},{"issue":"2","key":"716_CR70","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1287\/ijoc.13.2.96.10515","volume":"13","author":"H. P. Williams","year":"2001","unstructured":"Williams, H. P., & Yan, H. (2001). Representations of the all_different predicate of constraint satisfaction in integer programming. INFORMS Journal of Computing, 13(2), 96\u2013103.","journal-title":"INFORMS Journal of Computing"},{"issue":"5","key":"716_CR71","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"P. Zabala","year":"2006","unstructured":"Zabala, P., & M\u00e9ndez-D\u00edaz, I. (2006). A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5), 826\u2013847.","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"716_CR72","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6), 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-010-0716-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-010-0716-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-010-0716-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:08:00Z","timestamp":1559153280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-010-0716-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,30]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["716"],"URL":"https:\/\/doi.org\/10.1007\/s10479-010-0716-z","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,30]]}}}