Bimodal Depth-First Search for Scalable GAC for AllDifferent
Abstract
We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in O(n + ~m) time, where ~m is the sum, for each vertex v, of the minimum between the numbers of successors and non-successors of v. Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases, outperforming a GPU-accelerated version. In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.
Cite
Text
Le Bozec-Chiffoleau et al. "Bimodal Depth-First Search for Scalable GAC for AllDifferent." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/291Markdown
[Le Bozec-Chiffoleau et al. "Bimodal Depth-First Search for Scalable GAC for AllDifferent." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/bozecchiffoleau2025ijcai-bimodal/) doi:10.24963/IJCAI.2025/291BibTeX
@inproceedings{bozecchiffoleau2025ijcai-bimodal,
title = {{Bimodal Depth-First Search for Scalable GAC for AllDifferent}},
author = {Le Bozec-Chiffoleau, Sulian and Beldiceanu, Nicolas and Prud'homme, Charles and Simonin, Gilles and Lorca, Xavier},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {2610-2618},
doi = {10.24963/IJCAI.2025/291},
url = {https://mlanthology.org/ijcai/2025/bozecchiffoleau2025ijcai-bimodal/}
}