Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

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 edit...

Full description

Saved in:
Bibliographic Details
Published in:The ACM journal of experimental algorithmics 2023-05, Vol.28, p.1-13, Article 1.2
Main Authors: Crombez, Loïc, Da Fonseca, Guilherme D., Fontan, Florian, Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, Momège, Benjamin, Spalding-Jamieson, Jack, Zhang, Brandon, Zheng, Da Wei
Format: Article
Language:English
Subjects:
Computational Geometry
Computer Science
Design and analysis of algorithms
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1084-6654
1084-6654
DOI:10.1145/3588869