A new bidirectional ARC consistency algorithm

Arc consistency techniques have played an important role in constraint solving area. The paper presents a new bidirectional singleton arc consistency algorithm based on constraint networks, called BiSAC-2, and gives its correctness and completeness proof. BiSAC-2 shares the same simplification ability with BiSAC-1, furthermore, it decreases the times of keeping arc consistency. Namely, it avoids the redundant constraint propagation, and steadies more quickly than BiSAC-1.Finally the experiments on random constraint satisfaction problems show that BiSAC-2 has remarkable advantage over BiSAC-1 in performance.