{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:01:18Z","timestamp":1760367678370,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,4,4]],"date-time":"2017-04-04T00:00:00Z","timestamp":1491264000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["1376020"],"award-info":[{"award-number":["1376020"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s10732-017-9327-z","type":"journal-article","created":{"date-parts":[[2017,4,4]],"date-time":"2017-04-04T18:36:22Z","timestamp":1491330982000},"page":"321-343","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Tackling the edge dynamic graph colouring problem with and without future adjacency information"],"prefix":"10.1007","volume":"24","author":[{"given":"Bradley","family":"Hardy","sequence":"first","affiliation":[]},{"given":"Rhyd","family":"Lewis","sequence":"additional","affiliation":[]},{"given":"Jonathan","family":"Thompson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,4]]},"reference":[{"issue":"1","key":"9327_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K.I., Van Hoesel, S.P., Koster, A.M., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79\u2013129 (2007)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"9327_CR2","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1016\/j.cor.2006.05.014","volume":"35","author":"I Bl\u00f6chliger","year":"2008","unstructured":"Bl\u00f6chliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35(3), 960\u2013975 (2008)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"9327_CR3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251\u2013256 (1979)","journal-title":"Commun. ACM"},{"issue":"6","key":"9327_CR4","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"GJ Chaitin","year":"1982","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. ACM Sigplan Not. 17(6), 98\u2013101 (1982)","journal-title":"ACM Sigplan Not."},{"issue":"3","key":"9327_CR5","first-page":"161","volume":"33","author":"D Costa","year":"1995","unstructured":"Costa, D.: An evolutionary tabu search algorithm and the NHL scheduling problem. INFOR Inf. Syst. Oper. Res. 33(3), 161\u2013178 (1995)","journal-title":"INFOR Inf. Syst. Oper. Res."},{"issue":"1","key":"9327_CR6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ejor.2008.01.028","volume":"195","author":"A Dupont","year":"2009","unstructured":"Dupont, A., Linhares, A.C., Artigues, C., Feillet, D., Michelon, P., Vasquez, M.: The dynamic frequency assignment problem. Eur. J. Oper. Res. 195(1), 75\u201388 (2009)","journal-title":"Eur. J. Oper. Res."},{"key":"9327_CR7","doi-asserted-by":"crossref","unstructured":"Erben, W.: A grouping genetic algorithm for graph colouring and exam timetabling. In: Burke, E., Erben, W. (eds.) Practice and Theory of Automated Timetabling III. PATAT. Lecture Notes in Computer Science, vol 2079. Springer, Berlin, Heidelberg (2000)","DOI":"10.1007\/3-540-44629-X_9"},{"issue":"4","key":"9327_CR8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P Galinier","year":"1999","unstructured":"Galinier, P., Hao, J.K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379\u2013397 (1999)","journal-title":"J. Comb. Optim."},{"issue":"9","key":"9327_CR9","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.: A survey of local search methods for graph coloring. Comput. Oper. Res. 33(9), 2547\u20132562 (2006)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"9327_CR10","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S.: The complexity of near-optimal graph coloring. JACM 23(1), 43\u201349 (1976)","journal-title":"JACM"},{"key":"9327_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., San Francisco (1979)"},{"issue":"2","key":"9327_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: On-line and first fit colorings of graphs. J. Graph Theory 12(2), 217\u2013227 (1988)","journal-title":"J. Graph Theory"},{"issue":"7","key":"9327_CR13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0895-7177(97)00050-2","volume":"25","author":"F Harary","year":"1997","unstructured":"Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79\u201387 (1997)","journal-title":"Math. Comput. Model."},{"key":"9327_CR14","doi-asserted-by":"crossref","unstructured":"Hardy, B., Lewis, R., Thompson, J.: Modifying colourings between time-steps to tackle changes in dynamic random graphs. In: Chicano, F., Hu, B., Garc\u00eda-S\u00e1nchez, P. (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP. Lecture Notes in Computer Science, vol 9595. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-30698-8_13"},{"key":"9327_CR15","volume-title":"Graphs and Homomorphisms (Volume 28 of Oxford Lecture Series in Mathematics and its Applications)","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161etril, J.: Graphs and Homomorphisms (Volume 28 of Oxford Lecture Series in Mathematics and its Applications). Oxford University Press, Oxford (2004)"},{"issue":"13","key":"9327_CR16","doi-asserted-by":"crossref","first-page":"2551","DOI":"10.1016\/j.dam.2008.03.022","volume":"156","author":"A Hertz","year":"2008","unstructured":"Hertz, A., Plumettaz, M., Zufferey, N.: Variable space search for graph coloring. Discrete Appl. Math. 156(13), 2551\u20132560 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9327_CR17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345\u2013351 (1987)","journal-title":"Computing"},{"issue":"3","key":"9327_CR18","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"DS Johnson","year":"1991","unstructured":"Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Oper. Res. 39(3), 378\u2013406 (1991)","journal-title":"Oper. Res."},{"key":"9327_CR19","volume-title":"A Guide to Graph Colouring","author":"R Lewis","year":"2015","unstructured":"Lewis, R.: A Guide to Graph Colouring. Springer, Berlin (2015)"},{"issue":"11","key":"9327_CR20","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.1057\/jors.2016.34","volume":"67","author":"R Lewis","year":"2016","unstructured":"Lewis, R., Carroll, F.: Creating seating plans: a practical application. J. Oper. Res. Soc. 67(11), 1353\u20131362 (2016)","journal-title":"J. Oper. Res. Soc."},{"issue":"9","key":"9327_CR21","doi-asserted-by":"crossref","first-page":"1933","DOI":"10.1016\/j.cor.2011.08.010","volume":"39","author":"R Lewis","year":"2012","unstructured":"Lewis, R., Thompson, J., Mumford, C., Gillard, J.: A wide-ranging computational comparison of high-performance graph colouring algorithms. Comput. Oper. Res. 39(9), 1933\u20131950 (2012)","journal-title":"Comput. Oper. Res."},{"key":"9327_CR22","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/S0167-5060(08)70584-3","volume":"43","author":"L Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L., Saks, M., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Ann. Discret. Math. 43, 319\u2013325 (1989)","journal-title":"Ann. Discret. Math."},{"issue":"1","key":"9327_CR23","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.ejor.2009.07.016","volume":"203","author":"Z L\u00fc","year":"2010","unstructured":"L\u00fc, Z., Hao, J.K.: A memetic algorithm for graph coloring. Eur. J. Oper. Res. 203(1), 241\u2013250 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"9327_CR24","first-page":"381","volume":"6","author":"D Preuveneers","year":"2004","unstructured":"Preuveneers, D., Berbers, Y.: ACODYGRA: an agent algorithm for coloring dynamic graphs. Symb. Numer. Algorithms Sci. Comput. 6, 381\u2013390 (2004)","journal-title":"Symb. Numer. Algorithms Sci. Comput."},{"key":"9327_CR25","unstructured":"Qu, R., Burke, E.K., McCollum, B.: Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. Eur. J. Oper. Res. 198(2), 392\u2013404 (2009)"},{"key":"9327_CR26","doi-asserted-by":"crossref","unstructured":"Tantipathananandh, C., Berger-Wolf, T., Kempe, D.: A framework for community identification in dynamic social networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 717\u2013726. ACM (2007)","DOI":"10.1145\/1281192.1281269"},{"issue":"1","key":"9327_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"DJ Welsh","year":"1967","unstructured":"Welsh, D.J., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10(1), 85\u201386 (1967)","journal-title":"Comput. J."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-017-9327-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-017-9327-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-017-9327-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T12:10:10Z","timestamp":1568981410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-017-9327-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,4]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["9327"],"URL":"https:\/\/doi.org\/10.1007\/s10732-017-9327-z","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"type":"print","value":"1381-1231"},{"type":"electronic","value":"1572-9397"}],"subject":[],"published":{"date-parts":[[2017,4,4]]}}}