Consistent-Labeling Problems and Their Algorithms

Bernard Nudel

Two new classes of theories have been developed giving the expected complexities of three Consistent-Labeling Problem (CLP), or Constraint-Satisfaction, algorithms: Backtracking, Forward Checking and Word-wise Forward Checking. Apart from giving the exact expected complexity for these algorithms for the underlying CLP distribution and domain, these theories provide useful approximations for the complexity of solving essentially any individual CLP. Given this, and the fact that the theories can reflect changes in complexity due to changes in the ordering of variables used in the search, these theories have the potential to afford significant savings for any individual CLP, by predicting, prior to search, good orderings for use in solving that CLP. We are concurrently developing improved CLP algorithms based on this and similar ordering effects.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.