Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring

DOI10.1145/3588869MaRDI QIDQ6579767zbMATH OpenFDO

Authors Loïc Crombez, Guilherme D. Da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Dawei Zheng

Publication date 26 July 2024

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

zbMATH Keywords

graph coloringconstraint satisfaction problemsDIMACSCG:SHOP 2022

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3404264 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A branch-and-cut algorithm for graph coloring
• A graph coloring algorithm for large scheduling problems
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• An exact method for graph coloring
• An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Conflict-based local search for minimum partition into plane subgraphs (CG challenge)
• Exact solution of graph coloring problems via constraint programming and column generation
• Exact weighted vertex coloring via branch-and-price
• Hybrid evolutionary algorithms for graph coloring
• Local search with weighting schemes for the CG:SHOP 2022 competition (CG challenge)
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• New methods to color the vertices of a graph
• On Monte Carlo tree search for weighted vertex coloring
• Optimality clue for graph coloring problem
• Quantum annealing of the graph coloring problem
• SAT-based local search for plane subgraph partitions (CG challenge)
• Shadoks Approach to Low-Makespan Coordinated Motion Planning
• Shadoks approach to minimum partition into plane subgraphs (CG challenge)
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Using tabu search techniques for graph coloring

Cited in

(2)

• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• SAT-boosted tabu search for coloring massive graphs

This page was built for publication: Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6579767)