{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T12:43:36Z","timestamp":1774529016420,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this article, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs.<\/jats:p>","DOI":"10.1145\/3588869","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T12:10:10Z","timestamp":1679919010000},"page":"1-13","source":"Crossref","is-referenced-by-count":1,"title":["Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9542-5276","authenticated-orcid":false,"given":"Lo\u00efc","family":"Crombez","sequence":"first","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-028X","authenticated-orcid":false,"given":"Guilherme D.","family":"Da Fonseca","sequence":"additional","affiliation":[{"name":"LIS, Aix-Marseille Universit\u00e9, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0051-3514","authenticated-orcid":false,"given":"Florian","family":"Fontan","sequence":"additional","affiliation":[{"name":"Independent Researcher, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2664-0650","authenticated-orcid":false,"given":"Yan","family":"Gerard","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3226-7650","authenticated-orcid":false,"given":"Aldo","family":"Gonzalez-Lorenzo","sequence":"additional","affiliation":[{"name":"LIS, Aix-Marseille Universit\u00e9, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4459-511X","authenticated-orcid":false,"given":"Pascal","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9908-4811","authenticated-orcid":false,"given":"Luc","family":"Libralesso","sequence":"additional","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont Auvergne, Clermont-Fd, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8359-1210","authenticated-orcid":false,"given":"Benjamin","family":"Mom\u00e8ge","sequence":"additional","affiliation":[{"name":"Independent Researcher, Clermont-Ferrand, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1209-4345","authenticated-orcid":false,"given":"Jack","family":"Spalding-Jamieson","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8775-0709","authenticated-orcid":false,"given":"Brandon","family":"Zhang","sequence":"additional","affiliation":[{"name":"Independent Researcher, Vancouver, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0844-9457","authenticated-orcid":false,"given":"Da Wei","family":"Zheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.71"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524133"},{"issue":"2","key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"131","DOI":"10.7155\/jgaa.00064","article-title":"Small maximal independent sets and faster exact graph coloring","volume":"7","author":"Eppstein David","year":"2002","unstructured":"David Eppstein. 2002. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl 7, 2 (2002), 131\u2013140.","journal-title":"J. Graph Algorithms Appl"},{"key":"e_1_3_1_7_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. Journal of Experimental Algorithms 28 (2023).","journal-title":"Journal of Experimental Algorithms"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.73"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21716"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2012.03.002"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009823419804"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","unstructured":"Olivier Goudet Cyril Grelier and Jin-Kao Hao. 2022. A deep learning guided memetic framework for graph coloring problems. arXiv:2109.05948.","DOI":"10.1016\/j.knosys.2022.109986"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0436"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"key":"e_1_3_1_15_2","volume-title":"Graph Coloring Problems","author":"Jensen Tommy R.","year":"2011","unstructured":"Tommy R. Jensen and Bjarne Toft. 2011. Graph Coloring Problems. John Wiley & Sons."},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11\u201313, 1993","author":"Johnson David S.","year":"1996","unstructured":"David S. Johnson and Michael A. Trick. 1996. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11\u201313, 1993. Vol. 26. American Mathematical Society."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.084.024"},{"key":"e_1_3_1_18_2","volume-title":"A Guide to Graph Colouring: Algorithms and Applications (1st. ed.)","author":"Lewis R. M. R.","year":"2015","unstructured":"R. M. R. Lewis. 2015. A Guide to Graph Colouring: Algorithms and Applications (1st. ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.008"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3187-7.50015-5"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.4.344"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90007-K"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-017-9354-9"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.05.022"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.10.008"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.74"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2022.72"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.12.001"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0050060"},{"key":"e_1_3_1_30_2","unstructured":"Edward P. K. Tsang. 1993. Foundations of Constraint Satisfaction. Computation in Cognitive Science Academic Press. https:\/\/dblp.org\/rec\/books\/daglib\/0076790.bib."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588869","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:36Z","timestamp":1750178856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":30,"alternative-id":["10.1145\/3588869"],"URL":"https:\/\/doi.org\/10.1145\/3588869","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,11]]}}}