tant stability than MAC  the cpu time performances of Quick have a very low standard deviation It would be very interesting to propose efficient algorithms that maintain the local consistencies studied in this paper and to compare these algorithms  Such a study would allow us to know whether during search the more advantageous local consistencies remain RPC and Max RPC as during a preprocessing step  First results on the effect of maintaining SAC during search are given in   Prosser  Stergiou Wals h

## 7. Conclusion

In this paper we extended the idea of restricted path consistency to k RPC and Max RPC which are more pruningful local consistencies We proposed a new class of local consistencies called singleton consistencies We studied these new local consistencies and the other local consistencies that alike can be used on large CNs while removing more values than arc consistency  We showed some relations between them and we compared both theoretically and experimentally their pruning and time efficiencies  The most pruningful are neighborhood inverse consistency and singleton restricted path consistency  However SRPC is expensive in time and the exponential worst case time complexity of NIC makes it usable on dense CNs  If we are looking for a local consistency that would advantageously be maintained during search RPC and Max RPC seem to be the most promising local consistencies Indeed they are relatively inexpensive and far more pruningful than arc consistency

## 8. Acknowledgements

We would like to thank Toby Walsh for his suggestions for improving the presentation of the figures in Section

## References

Maintaining Knowledge about Temporal Intervals Communications of Allen J
the ACM 26(11)
Bacchus   F
van Run P
Dynamic variable ordering in csps In Proceedings of CP-95, Cassis, France pp Berlandier P
Improving domain filtering using restricted path consistency I n Proceedings of IEEE CAIA-95 Bessiere C Freuder E
Regin J
Using inference to reduce arc consistency computation  In Proceedings of IJCAI-95, Montréal, Canada  pp Using constraint metaknowledge to reduce Bessiere C Freuder E
Regin J
arc consistency computation  Artificial Intelligence  107(1)
MAC and combined heuristics  Two reasons to forsake FC
Bessiere C
Regin J
and CBJ   on hard problems  In Proceedings of CP-96, Cambridge MA  pp