caa a22 4500 44587922X CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s10601-009-9080-5 doi (NATIONALLICENCE)springer-10.1007/s10601-009-9080-5 Efficient algorithms for singleton arc consistency [Elektronische Daten] [Christian Bessiere, Stéphane Cardon, Romuald Debruyne, Christophe Lecoutre] In this paper, we propose two original and efficient approaches for enforcing singleton arc consistency. In the first one, the data structures used to enforce arc consistency are shared between all subproblems where a domain is reduced to a singleton. This new algorithm is not optimal but it requires far less space and is often more efficient in practice than the optimal algorithm SAC-Opt. In the second approach, we perform several runs of a greedy search (where at each step, arc consistency is maintained), possibly detecting the singleton arc consistency of several values in one run. It is an original illustration of applying inference (i.e., establishing singleton arc consistency) by search. Using a greedy search allows benefiting from the incrementality of arc consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. We present extensive experiments that show the benefit of our two approaches. Springer Science+Business Media, LLC, 2009 Singleton arc consistency nationallicence Filtering nationallicence Constraint propagation nationallicence Local consistency nationallicence Bessiere Christian LIRMM-CNRS, Université de Montpellier, Montpellier, France aut Cardon Stéphane CRIL-CNRS, Université d'artois, Lens, France aut Debruyne Romuald LINA-CNRS, Ecole des Mines de Nantes, Nantes, France aut Lecoutre Christophe CRIL-CNRS, Université d'artois, Lens, France aut Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 25-53 1383-7133 16:1<25 2011 16 10601 https://doi.org/10.1007/s10601-009-9080-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-009-9080-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bessiere Christian LIRMM-CNRS, Université de Montpellier, Montpellier, France aut NATIONALLICENCE 700 1- Cardon Stéphane CRIL-CNRS, Université d'artois, Lens, France aut NATIONALLICENCE 700 1- Debruyne Romuald LINA-CNRS, Ecole des Mines de Nantes, Nantes, France aut NATIONALLICENCE 700 1- Lecoutre Christophe CRIL-CNRS, Université d'artois, Lens, France aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 25-53 1383-7133 16:1<25 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer