We present a detailed study of two inverse consistencies for non-binary constraints: relational path inverse consistency (rel PIC) and pairwise inverse consistency (PWIC). These are stronger than generalized arc consistency (GAC), even though they also only prune domain values. We propose algorithms to achieve rel PIC and PWIC, that have a time complexity better than the previous generic algorithm for inverse consistencies. One of our algorithms for PWIC has a complexity comparable to that for GAC despite doing more pruning. Our experiments demonstrate that inverse consistencies can be more efficient than GAC on a range of non-binary problems.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com