{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:17:39Z","timestamp":1757542659095,"version":"3.37.3"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Google Research Latin America","award":["25111"],"award-info":[{"award-number":["25111"]}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["142087\/2018-1"],"award-info":[{"award-number":["142087\/2018-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10732-021-09487-9","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:05:01Z","timestamp":1642982701000},"page":"61-91","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A new heuristic for finding verifiable k-vertex-critical subgraphs"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6613-3998","authenticated-orcid":false,"given":"Alex","family":"Gliesch","sequence":"first","affiliation":[]},{"given":"Marcus","family":"Ritt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"9487_CR1","doi-asserted-by":"publisher","unstructured":"Barba, L., Cardinal, J., Korman, M., Langerman, S., Van\u00a0Renssen, A., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: Workshop on Algorithms and Data Structures, pp. 97\u2013108. Springer (2017). https:\/\/doi.org\/10.1109\/CCCA.2011.6031437","DOI":"10.1109\/CCCA.2011.6031437"},{"key":"9487_CR2","doi-asserted-by":"publisher","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities\u2014an $$O(n^{1\/4})$$ approximation for densest $$k$$-Subgraph. In: 42nd ACM Symposium on Theory of Computing, p. 201. ACM Press, New York, NY, USA (2010). https:\/\/doi.org\/10.1145\/1806689.1806719","DOI":"10.1145\/1806689.1806719"},{"key":"9487_CR3","unstructured":"Bl\u00f6chliger, I., Zufferey, N.: A reactive tabu search using partial solutions for the graph coloring problem. Tech. Rep. 04\/03, \u00c9cole PolyTechnique F\u00e9d\u00e9rale de Lausanne (2004)"},{"issue":"3","key":"9487_CR4","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.cor.2006.05.014","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"9487_CR5","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1016\/j.ejor.2017.04.034","volume":"262","author":"N Bourgeois","year":"2017","unstructured":"Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V.T.: Exact and superpolynomial approximation algorithms for the densest $$k$$-subgraph problem. Eur. J. Oper. Res. 262(3), 894\u2013903 (2017). https:\/\/doi.org\/10.1016\/j.ejor.2017.04.034","journal-title":"Eur. J. Oper. Res."},{"issue":"11","key":"9487_CR6","doi-asserted-by":"publisher","first-page":"2885","DOI":"10.1016\/j.cor.2008.12.020","volume":"36","author":"J Brimberg","year":"2009","unstructured":"Brimberg, J., Mladenovi\u0107, N., Uro\u0161evi\u0107, D., Ngai, E.: Variable neighborhood search for the heaviest $$k$$-subgraph. Comput. Oper. Res. 36(11), 2885\u20132891 (2009). https:\/\/doi.org\/10.1016\/j.cor.2008.12.020","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"9487_CR7","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Cambridge Philos. Soc. 37(2), 194\u2013197 (1941). https:\/\/doi.org\/10.1017\/S030500410002168X","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"9487_CR8","doi-asserted-by":"publisher","unstructured":"Caramia, M., Dell\u2019Olmo, P.: Bounding vertex coloring by truncated multistage branch and bound. Networks 44(4), 231\u2013242 (2004). https:\/\/doi.org\/10.1002\/net.20035","DOI":"10.1002\/net.20035"},{"key":"9487_CR9","doi-asserted-by":"publisher","unstructured":"Caramia, M., Dell\u2019Olmo, P.: Coloring graphs by iterated local search traversing feasible and infeasible solutions. Disc. Appl. Math. 156(2), 201\u2013217 (2008). https:\/\/doi.org\/10.1016\/j.dam.2006.07.013","DOI":"10.1016\/j.dam.2006.07.013"},{"issue":"9","key":"9487_CR10","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1016\/j.ipl.2014.04.009","volume":"114","author":"M Chang","year":"2014","unstructured":"Chang, M., Chen, L., Hung, L., Rossmanith, P., Wu, G.: Exact algorithms for problems related to the densest $$k$$-set problem. Inform. Process. Lett. 114(9), 510\u2013513 (2014). https:\/\/doi.org\/10.1016\/j.ipl.2014.04.009","journal-title":"Inform. Process. Lett."},{"key":"9487_CR11","unstructured":"Culberson, J.C.: Quasi-random coloring problem (1995). https:\/\/mat.tepper.cmu.edu\/COLOR\/instances.html#XXCUL. Accessed June 9th, 2020"},{"key":"9487_CR12","unstructured":"Culberson, J.C.: Graph coloring programs manual (1997). https:\/\/webdocs.cs.ualberta.ca\/~joe\/Coloring\/Colorsrc\/manual.html#bkdsatur. Accessed June 9th, 2020"},{"key":"9487_CR13","unstructured":"de\u00a0Grey, A.: The chromatic number of the plane is at least 5 (2018). ArXiv:1804.02385"},{"issue":"2","key":"9487_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.dam.2006.07.019","volume":"156","author":"C Desrosiers","year":"2008","unstructured":"Desrosiers, C., Galinier, P., Hertz, A.: Efficient algorithms for finding critical subgraphs. Disc. Appl. Math. 156(2), 244\u2013266 (2008). https:\/\/doi.org\/10.1016\/j.dam.2006.07.019","journal-title":"Disc. Appl. Math."},{"key":"9487_CR15","doi-asserted-by":"publisher","unstructured":"Dirac, G.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. s3\u20132(1), 69\u201381 (1952). https:\/\/doi.org\/10.1112\/plms\/s3-2.1.69","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"9487_CR16","first-page":"2001","volume":"29","author":"U Feige","year":"1997","unstructured":"Feige, U., Seltser, M.: On the densest $$k$$-subgraph problem. Algorithmica 29, 2001 (1997)","journal-title":"Algorithmica"},{"issue":"2","key":"9487_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6(2), 109\u2013133 (1995). https:\/\/doi.org\/10.1007\/BF01096763","journal-title":"J. Global Optim."},{"key":"9487_CR18","unstructured":"Funabiki, N., Higashino, T.: A minimal-state processing search algorithm for graph colorings problems. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E83-A (2000)"},{"issue":"4","key":"9487_CR19","doi-asserted-by":"publisher","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. Combin. Optim. 3(4), 379\u2013397 (1999). https:\/\/doi.org\/10.1023\/A:1009823419804","journal-title":"J. Combin. Optim."},{"issue":"3","key":"9487_CR20","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/j.dam.2006.04.043","volume":"155","author":"P Galinier","year":"2007","unstructured":"Galinier, P., Hertz, A.: Solution techniques for the large set covering problem. Disc. Appl. Math. 155(3), 312\u2013326 (2007). https:\/\/doi.org\/10.1016\/j.dam.2006.04.043","journal-title":"Disc. Appl. Math."},{"issue":"2","key":"9487_CR21","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.dam.2006.07.017","volume":"156","author":"P Galinier","year":"2008","unstructured":"Galinier, P., Hertz, A., Zufferey, N.: An adaptive memory algorithm for the $$k$$-coloring problem. Disc. Appl. Math. 156(2), 267\u2013279 (2008). https:\/\/doi.org\/10.1016\/j.dam.2006.07.017","journal-title":"Disc. Appl. Math."},{"key":"9487_CR22","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., New York, NY, USA (1979)"},{"key":"9487_CR23","doi-asserted-by":"publisher","unstructured":"Glover, F., L\u00fc, Z., Hao, J.K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR 8(3), 239\u2013253 (2010). https:\/\/doi.org\/10.1007\/s10288-009-0115-y","DOI":"10.1007\/s10288-009-0115-y"},{"key":"9487_CR24","unstructured":"Gomes, C.P., Shmoys, D.: Completing quasigroups or Latin squares: a structured graph coloring problem. In: Computational Symposium on Graph Coloring and Generalizations (2002)"},{"issue":"1","key":"9487_CR25","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1287\/ijoc.1100.0436","volume":"24","author":"S Gualandi","year":"2012","unstructured":"Gualandi, S., Malucelli, F.: Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1), 81\u2013100 (2012). https:\/\/doi.org\/10.1287\/ijoc.1100.0436","journal-title":"INFORMS J. Comput."},{"key":"9487_CR26","first-page":"116","volume":"10","author":"G Haj\u00f3s","year":"1961","unstructured":"Haj\u00f3s, G.: \u00dcber eine Konstruktion nicht $$n$$-f\u00e4rbbarer Graphen. Wissenschaftliche Zeitschrift der Martin-Luther-Universitat Halle-Wittenberg 10, 116\u2013117 (1961)","journal-title":"Wissenschaftliche Zeitschrift der Martin-Luther-Universitat Halle-Wittenberg"},{"issue":"16\u201317","key":"9487_CR27","doi-asserted-by":"publisher","first-page":"2397","DOI":"10.1016\/j.dam.2012.06.007","volume":"160","author":"JK Hao","year":"2012","unstructured":"Hao, J.K., Wu, Q.: Improving the extraction and expansion method for large graph coloring. Disc. Appl. Math. 160(16\u201317), 2397\u20132407 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.06.007","journal-title":"Disc. Appl. Math."},{"key":"9487_CR28","doi-asserted-by":"publisher","unstructured":"Held, S., Cook, W., Sewell, E.C.: Safe lower bounds for graph coloring. In: International Conference on Integer Programming and Combinatorial Optimization, vol. 6655 LNCS, pp. 261\u2013273 (2011). https:\/\/doi.org\/10.1007\/978-3-642-20807-2_21","DOI":"10.1007\/978-3-642-20807-2_21"},{"issue":"212","key":"9487_CR29","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1145\/944618.944628","volume":"5","author":"F Herrmann","year":"2000","unstructured":"Herrmann, F., Hertz, A.: Finding the chromatic number by means of critical graphs. Electron. Notes Disc. Math. 5(212), 174\u2013176 (2000). https:\/\/doi.org\/10.1145\/944618.944628","journal-title":"Electron. Notes Disc. Math."},{"issue":"4","key":"9487_CR30","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz, A., Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345\u2013351 (1987). https:\/\/doi.org\/10.1007\/BF02239976","journal-title":"Computing"},{"issue":"13","key":"9487_CR31","doi-asserted-by":"publisher","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. Disc. Appl. Math. 156(13), 2551\u20132560 (2008). https:\/\/doi.org\/10.1016\/j.dam.2008.03.022","journal-title":"Disc. Appl. Math."},{"issue":"1","key":"9487_CR32","first-page":"32","volume":"I","author":"MJH Heule","year":"2019","unstructured":"Heule, M.J.H.: Computing small unit-distance graphs with chromatic number 5. Geocombinatorics XXVII I(1), 32\u201350 (2019a)","journal-title":"Geocombinatorics XXVII"},{"key":"9487_CR33","doi-asserted-by":"publisher","unstructured":"Heule, M.J.H.: Trimming graphs using clausal proof optimization. In: Proc. Int. Conf. Princ. Pract. Constr. Progr., pp. 251\u2013267 (2019b). https:\/\/doi.org\/10.1007\/978-3-030-30048-7_15","DOI":"10.1007\/978-3-030-30048-7_15"},{"key":"9487_CR34","doi-asserted-by":"publisher","unstructured":"Johnson, D., Trick, M. (eds.): Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, Providence, Rhode Island (1996). https:\/\/doi.org\/10.1090\/dimacs\/026","DOI":"10.1090\/dimacs\/026"},{"key":"9487_CR35","unstructured":"Korman, S.M.: The graph-colouring problem. In: Combinatorial Optimization, pp. 211\u2013235. Wiley (1979)"},{"issue":"9","key":"9487_CR36","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.cor.2011.08.010","journal-title":"Comput. Oper. Res."},{"key":"9487_CR37","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","volume":"3","author":"M L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez, M., Dubois-Lacoste, J., P\u00e9rez C\u00e1ceres, L., Birattari, M., St\u00fctzle, T.: The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43\u201358 (2016). https:\/\/doi.org\/10.1016\/j.orp.2016.09.002","journal-title":"Oper. Res. Perspect."},{"issue":"1","key":"9487_CR38","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.ejor.2009.07.016","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"9487_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2010","unstructured":"Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17(1), 1\u201334 (2010). https:\/\/doi.org\/10.1111\/j.1475-3995.2009.00696.x","journal-title":"Int. Trans. Oper. Res."},{"issue":"2","key":"9487_CR40","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1287\/ijoc.1070.0245","volume":"20","author":"E Malaguti","year":"2008","unstructured":"Malaguti, E., Monaci, M., Toth, P.: A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. 20(2), 302\u2013316 (2008). https:\/\/doi.org\/10.1287\/ijoc.1070.0245","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"9487_CR41","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2010.07.005","volume":"8","author":"E Malaguti","year":"2011","unstructured":"Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Disc. Optim. 8(2), 174\u2013190 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.07.005","journal-title":"Disc. Optim."},{"key":"9487_CR42","doi-asserted-by":"publisher","unstructured":"Manurangsi, P.: Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 954\u2013961 (2017). https:\/\/doi.org\/10.1145\/3055399.3055412","DOI":"10.1145\/3055399.3055412"},{"issue":"4","key":"9487_CR43","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A Mehrotra","year":"1996","unstructured":"Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344\u2013354 (1996). https:\/\/doi.org\/10.1287\/ijoc.8.4.344","journal-title":"INFORMS J. Comput."},{"issue":"5","key":"9487_CR44","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"I M\u00e9ndez-D\u00edaz","year":"2006","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A branch-and-cut algorithm for graph coloring. Disc. Appl. Math. 154(5), 826\u2013847 (2006). https:\/\/doi.org\/10.1016\/j.dam.2005.05.022","journal-title":"Disc. Appl. Math."},{"issue":"2","key":"9487_CR45","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.dam.2006.07.010","volume":"156","author":"I M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A cutting plane algorithm for graph coloring. Disc. Appl. Math. 156(2), 159\u2013179 (2008). https:\/\/doi.org\/10.1016\/j.dam.2006.07.010","journal-title":"Disc. Appl. Math."},{"key":"9487_CR46","doi-asserted-by":"publisher","unstructured":"Moalic, L., Gondran, A.: The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity. In: European Conference on Evolutionary Computation in Combinatorial Optimization, vol. 9026 LNCS, pp. 173\u2013183 (2015). https:\/\/doi.org\/10.1007\/978-3-319-16468-7_15","DOI":"10.1007\/978-3-319-16468-7_15"},{"key":"9487_CR47","unstructured":"Parts, J.: Polymath16, thirteenth thread: Bumping the deadline?\u2014Short, Fat Matrices (2019). https:\/\/dustingmixon.wordpress.com\/2019\/07\/08\/polymath16-thirteenth-thread-bumping-the-deadline\/#comment-23999. Accessed June 9th, 2020"},{"key":"9487_CR48","unstructured":"Polymath Wiki Contributors.: Hadwiger-Nelson problem\u2014Polymath Wiki (2020). http:\/\/michaelnielsen.org\/polymath1\/index.php?title=Hadwiger-Nelson_problem. Accessed June 9th, 2020"},{"issue":"10","key":"9487_CR49","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.cor.2010.01.015","volume":"37","author":"DC Porumbel","year":"2010","unstructured":"Porumbel, D.C., Hao, J.K., Kuntz, P.: An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37(10), 1822\u20131832 (2010). https:\/\/doi.org\/10.1016\/j.cor.2010.01.015","journal-title":"Comput. Oper. Res."},{"issue":"7","key":"9487_CR50","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1016\/j.cor.2011.10.008","volume":"39","author":"PS Segundo","year":"2012","unstructured":"Segundo, P.S.: A new DSATUR-based algorithm for exact vertex coloring. Comput. Oper. Res. 39(7), 1724\u20131733 (2012). https:\/\/doi.org\/10.1016\/j.cor.2011.10.008","journal-title":"Comput. Oper. Res."},{"key":"9487_CR51","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cor.2013.11.015","volume":"45","author":"K Smith-Miles","year":"2014","unstructured":"Smith-Miles, K., Baatar, D., Wreford, B., Lewis, R.: Towards objective measures of algorithm performance across instance space. Comput. Oper. Res. 45, 12\u201324 (2014). https:\/\/doi.org\/10.1016\/j.cor.2013.11.015","journal-title":"Comput. Oper. Res."},{"key":"9487_CR52","doi-asserted-by":"publisher","unstructured":"Soifer, A.: The Mathematical Coloring Book. Springer, New York, NY, USA (2009). https:\/\/doi.org\/10.1007\/978-0-387-74642-5","DOI":"10.1007\/978-0-387-74642-5"},{"issue":"4\u20135","key":"9487_CR53","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10732-017-9358-5","volume":"25","author":"W Sun","year":"2019","unstructured":"Sun, W., Hao, J.K., Caminada, A.: Iterated backtrack removal search for finding $$k$$-vertex-critical subgraphs. J. Heurist. 25(4\u20135), 565\u2013590 (2019). https:\/\/doi.org\/10.1007\/s10732-017-9358-5","journal-title":"J. Heurist."},{"key":"9487_CR54","doi-asserted-by":"publisher","unstructured":"Titiloye, O., Crispin, A.: Graph coloring with a distributed hybrid quantum annealing algorithm. In: KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications, vol. 6682 LNAI, pp. 553\u2013562 (2011a). https:\/\/doi.org\/10.1007\/978-3-642-22000-5_57","DOI":"10.1007\/978-3-642-22000-5_57"},{"issue":"2","key":"9487_CR55","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/j.disopt.2010.12.001","volume":"8","author":"O Titiloye","year":"2011","unstructured":"Titiloye, O., Crispin, A.: Quantum annealing of the graph coloring problem. Discrete Optimization 8(2), 376\u2013384 (2011b). https:\/\/doi.org\/10.1016\/j.disopt.2010.12.001","journal-title":"Discrete Optimization"},{"issue":"11","key":"9487_CR56","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0050060","volume":"7","author":"O Titiloye","year":"2012","unstructured":"Titiloye, O., Crispin, A.: Parameter tuning patterns for random graph coloring with quantum annealing. PLoS ONE 7(11), e50060 (2012). https:\/\/doi.org\/10.1371\/journal.pone.0050060","journal-title":"PLoS ONE"},{"key":"9487_CR57","doi-asserted-by":"publisher","first-page":"667","DOI":"10.2197\/ipsjjip.25.667","volume":"25","author":"E Tomita","year":"2017","unstructured":"Tomita, E., Matsuzaki, S., Nagao, A., Ito, H., Wakatsuki, M.: A much faster algorithm for finding a maximum clique with computational experiments. J. Inform. Process. 25, 667\u2013677 (2017). https:\/\/doi.org\/10.2197\/ipsjjip.25.667","journal-title":"J. Inform. Process."},{"key":"9487_CR58","volume-title":"Foundations of Constraint Satisfaction","author":"E Tsang","year":"1993","unstructured":"Tsang, E.: Foundations of Constraint Satisfaction. Academic Press, London (1993)"},{"key":"9487_CR59","unstructured":"Wu, Q.: The maximum clique problems with applications to graph coloring. PhD thesis, Universit\u00e9 d\u2019Angers (2013)"},{"key":"9487_CR60","doi-asserted-by":"publisher","unstructured":"Wu, Q., Hao, J.K.: An extraction and expansion approach for graph coloring. Asia-Pacific J. Oper. Res. 30(5) (2013). https:\/\/doi.org\/10.1142\/S0217595913500188","DOI":"10.1142\/S0217595913500188"},{"issue":"1","key":"9487_CR61","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/s10479-012-1124-3","volume":"196","author":"Q Wu","year":"2012","unstructured":"Wu, Q., Hao, J.K., Glover, F.: Multi-neighborhood tabu search for the maximum weight clique problem. Ann. Oper. Res. 196(1), 611\u2013634 (2012). https:\/\/doi.org\/10.1007\/s10479-012-1124-3","journal-title":"Ann. Oper. Res."},{"key":"9487_CR62","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/j.eswa.2016.07.047","volume":"64","author":"Y Zhou","year":"2016","unstructured":"Zhou, Y., Hao, J.K., Duval, B.: Reinforcement learning based local search for grouping problems: a case study on graph coloring. Exp. Syst. Appl. 64, 412\u2013422 (2016). https:\/\/doi.org\/10.1016\/j.eswa.2016.07.047","journal-title":"Exp. Syst. Appl."},{"key":"9487_CR63","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.asoc.2018.01.027","volume":"65","author":"Y Zhou","year":"2018","unstructured":"Zhou, Y., Duval, B., Hao, J.K.: Improving probability learning based local search for graph coloring. Appl. Soft Comput. J. 65, 542\u2013553 (2018). https:\/\/doi.org\/10.1016\/j.asoc.2018.01.027","journal-title":"Appl. Soft Comput. J."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09487-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-021-09487-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09487-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T09:04:53Z","timestamp":1645434293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-021-09487-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["9487"],"URL":"https:\/\/doi.org\/10.1007\/s10732-021-09487-9","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"type":"print","value":"1381-1231"},{"type":"electronic","value":"1572-9397"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"17 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}