

![0_image_0.png](0_image_0.png)

completability
difficulties to delete inconsistent values on dense problems with loose constraints On sparse CNs the polynomial local consistencies studied are close to variable completability whereas on very dense CNs  Figure   and Figure   show alarge range of tight nesses between them and variable completability NIC behaves very differently since on complete constraint networks it corresponds to variable completability So on dense CNs NIC is far more pruningful than the other local consistencies On CNs generated with a density lower than NIC
is less pruningful than SRPC strong PC and SAC The more important the propagation through the network is  the closer To and Tall are  If a filtering  such as AC  uses a very local property to delete inconsistent values  there is a large set of CNs on which it removes ssee and the complement of the complement of the complement of the complement of the complement of the complement of the complement that the part of the network to know whether a value is consistent or not  So  they seldom delete few values On most of the CNs they do not delete any value or detect inconsistency the propagation of the first value deletions often leads to a domain wipe out

## 6. Time Efficiency 6.1 Radio Link Frequency Assignment Problems

An experimental evaluation has been done on the radio link frequency assignment problems described in Cabon de Givry Lobjois Schiex Warners namely the instances of the CELAR 4 named Scen to Scen and the GRAPH instances generated using the GRAPH generator at Delft University named Graph   to Graph     In these problems we have to assign frequencies to a set of radio links defined between pairs of sites in order to to avoid interferences 5 These problems have from variables and there are to val ues in average in each domain The constraints are binary and have a cost of violation specified