Improved bounds on the complexity of kB-consistency
Lucas Bordeaux, Éric Monfroy, Frédéric Benhamou · 2001
Abstract-consistencies form the class of strong consis-tencies used in interval constraint programming. We survey, prove, and give theoretical motivations to some technical improvements to a naive ¢¤£ consistency algorithm. Our contribution is twofold: on the one hand, we introduce an ¥ optimal-consistency algorithm whose time-complexity ¦¨§�©�������� of improves the known bound by a � factor is the number of constraints, � is the number of variables, and � is the maximal size of the intervals of the box). On the other hand, we prove that improved bounds on time complexity can effectively be reached for higher values of ¢. These results are obtained with very affordable overheads in terms of space complexity.