Skip to main content
padlock icon - secure page this page is secure

Backtracking along with constraint processing and their time complexities

Buy Article:

$60.00 + tax (Refund Policy)

In this review paper we embed several constraint propagation algorithms inside a backtracking algorithm in order to solve constraint satisfaction problems and analyse the time complexities. To get a common frame for presenting the diverse algorithms we provide formal definitions for a uniform treatment of constraint satisfaction problems. For some constraint satisfaction algorithms we prove that their asymptotic total worst-case time complexities are equal to that of ordinary backtracking. If the constraint satisfaction problems are binary, the asymptotic total worst-case time complexities of these algorithms are even better and optimal in the sense that there is no algorithm which improves these complexity bounds. Furthermore, we present a new algorithm that establishes global consistency.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
No Metrics

Keywords: BACKTRACKING CONSTRAINT PROPAGATION LOCAL AND GLOBAL CONSISTENCY COMPUTATIONAL COMPLEXITY

Document Type: Research Article

Publication date: January 1, 1996

More about this publication?
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
X
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more