New Algorithms for Bidirectional Singleton Arc Consistency

Yonggang Zhang, Qian Yin, Xingjun Zhu, Zhanshan Li, Sibo Zhang and Quan Liu

Mathematical Problems in Engineering, 2013, vol. 2013, 1-10

Abstract:

Bidirectional singleton arc consistency (BiSAC) which is an extended singleton arc consistency (SAC) has been proposed recently. The first contribution of this paper is to propose and prove two theorems of BiSAC theoretically (one is a property of BiSAC and the other is the property of allowing the deletion of some BiSAC-inconsistent values). Secondly, based on these properties we present two algorithms, denoted by BiSAC-DF and BiSAC-DP, to enforce BiSAC. Also, we prove their correctness and analyze the space and time complexity of them in detail. Besides, for special circumstances, we show that BiSAC-DF admits a worst-case time complexity in and a best one in when the problem is an already BiSAC, while BiSAC-DP also has the same best one when the tightness is small. Finally, experiments on a wide range of CSP instances show BiSAC-DF and BiSAC-DP are usually around one order of magnitude faster than the existing BiSAC-1. For some special instances, BiSAC-DP is about two orders of magnitude efficient.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/904768.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/904768.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:904768

DOI: 10.1155/2013/904768

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().