{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T12:57:08Z","timestamp":1768568228213,"version":"3.49.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T00:00:00Z","timestamp":1690243200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["P32441, P36420, and W1255"],"award-info":[{"award-number":["P32441, P36420, and W1255"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["ICT19-065"],"award-info":[{"award-number":["ICT19-065"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Graph coloring is the problem of coloring the vertices of a graph with as few colors as possible, avoiding monochromatic edges. It is one of the most fundamental NP-hard computational problems. For decades researchers have developed exact and heuristic methods for graph coloring. While methods based on propositional satisfiability (SAT) feature prominently among these exact methods, the encoding size is prohibitive for large graphs. For such graphs, heuristic methods have been proposed, with tabu search among the most successful ones.<\/jats:p>\n          <jats:p>In this article, we enhance tabu search for graph coloring within the SAT-based local improvement (SLIM) framework. Our hybrid algorithm incrementally improves a candidate solution by repeatedly selecting small subgraphs and coloring them optimally with a SAT solver. This approach scales to dense graphs with several hundred thousand vertices and over 1.5 billion edges. Our experimental evaluation shows that our hybrid algorithm beats state-of-the-art methods on large dense graphs.<\/jats:p>","DOI":"10.1145\/3603112","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T11:43:37Z","timestamp":1685447017000},"page":"1-19","source":"Crossref","is-referenced-by-count":5,"title":["SAT-boosted Tabu Search for Coloring Massive Graphs"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6790-7158","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schidler","sequence":"first","affiliation":[{"name":"TU Wien, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8994-1656","authenticated-orcid":false,"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}]}],"member":"320","published-online":{"date-parts":[[2023,7,25]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"399","volume-title":"IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11\u201317, 2009","author":"Audemard Gilles","year":"2009","unstructured":"Gilles Audemard and Laurent Simon. 2009. Predicting learnt clauses quality in modern SAT solvers. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11\u201317, 2009, Craig Boutilier (Ed.). 399\u2013404. Retrieved from http:\/\/ijcai.org\/Proceedings\/09\/Papers\/074.pdf."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_8"},{"key":"e_1_3_2_4_2","first-page":"51","volume-title":"Proc. of SAT Competition 2020 \u2013 Solver and Benchmark Descriptions (Department of Computer Science Report Series B)","author":"Biere Armin","year":"2020","unstructured":"Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. 2020. CaDiCaL, KISSAT, PARACOOBA, PLINGELING and TREENGELING entering the SAT competition 2020. In Proc. of SAT Competition 2020 \u2013 Solver and Benchmark Descriptions (Department of Computer Science Report Series B), Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti J\u00e4rvisalo, and Martin Suda (Eds.), Vol. B-2020-1. University of Helsinki, 51\u201353."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0716-z"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_9_2","article-title":"Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring","volume":"28","author":"Crombez Lo\u00efc","year":"2023","unstructured":"Lo\u00efc Crombez, Guilherme Dias da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Mom\u00e8ge, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. 2023. Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring. J. Experim. Algor. 28 (2023). This issue.","journal-title":"J. Experim. Algor."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.71"},{"key":"e_1_3_2_11_2","article-title":"Minimum partition into plane subgraphs: The CG:SHOP challenge 2022","volume":"28","author":"Fekete S\u00e1ndor P.","year":"2023","unstructured":"S\u00e1ndor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. 2023. Minimum partition into plane subgraphs: The CG:SHOP challenge 2022. J. Experim. Algor. 28 (2023). This issue.","journal-title":"J. Experim. Algor."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.026"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3560469"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66263-3_25"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.73"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.10"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30048-7_13"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.06.007"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/856"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19212-9_25"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.67"},{"key":"e_1_3_2_23_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"issue":"3","key":"e_1_3_2_25_2","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin Leonid","year":"1973","unstructured":"Leonid Levin. 1973. Universal sequential search problems. Prob. Inf. Transmiss. 9, 3 (1973), 265\u2013266.","journal-title":"Prob. Inf. Transmiss."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/73"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66263-3_27"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3326159"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026\/16"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5_13"},{"key":"e_1_3_2_31_2","first-page":"3895","volume-title":"Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, the Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2\u20139, 2021","author":"Ramaswamy Vaidyanathan Peruvemba","year":"2021","unstructured":"Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. 2021. Turbocharging treewidth-bounded Bayesian network structure learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, the Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2\u20139, 2021. AAAI Press, 3895\u20133903.Retrieved from https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/16508."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i4.25524"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0228-y"},{"key":"e_1_3_2_34_2","first-page":"3904","volume-title":"Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, the Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2\u20139, 2021","author":"Schidler Andr\u00e9","year":"2021","unstructured":"Andr\u00e9 Schidler and Stefan Szeider. 2021. SAT-based decision tree learning for large data sets. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, the Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2\u20139, 2021. AAAI Press, 3904\u20133912. Retrieved from https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/16509."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.72"},{"key":"e_1_3_2_36_2","volume-title":"Heuristic Algorithms for Graph Coloring Problems. (Algorithmes heuristiques pour des probl\u00e8mes de coloration de graphes)","author":"Sun Wen","year":"2018","unstructured":"Wen Sun. 2018. Heuristic Algorithms for Graph Coloring Problems. (Algorithmes heuristiques pour des probl\u00e8mes de coloration de graphes). Ph.D. Dissertation. University of Angers, France. Retrieved from https:\/\/tel.archives-ouvertes.fr\/tel-02136810."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2578043"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2014.0618"},{"key":"e_1_3_2_39_2","unstructured":"Marinka Zitnik Rok Sosi\u010d Sagar Maheshwari and Jure Leskovec. 2018. BioSNAP Datasets: Stanford Biomedical Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/biodata."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603112","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3603112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:29:51Z","timestamp":1750285791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,25]]},"references-count":38,"alternative-id":["10.1145\/3603112"],"URL":"https:\/\/doi.org\/10.1145\/3603112","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,25]]}}}