New algorithms for bidirectional singleton arc consistency
type: Item
instance of: scholarly article
title: New algorithms for bidirectional singleton arc consistency
zbMATH Open document ID: 1299.68150
DOI: 10.1155/2013/904768
author: Qian Yin
author: Xingjun Zhu
author: Zhanshan Li
author: Sibo Zhang
author: Quan Liu
author: Yonggang Zhang
published in: Mathematical Problems in Engineering
publication date: 2014-11-24T00:00:00Z
review text: Summary: 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 \(O(en^2d^4)\) and a best one in \(O(en^2d^3)\) 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.
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 6373257
Wikidata QID: Q59029432
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/904768
OpenAlex ID: W1985829054
cites work: An optimal coarse-grained arc consistency algorithm
cites work: Consistency in networks of relations
cites work: Q4473037
cites work: Theoretical analysis of singleton arc consistency and its extensions
cites work: Random constraint satisfaction: Flaws and structure
Recommended article: Efficient algorithms for singleton arc consistency
Recommended article: Theoretical analysis of singleton arc consistency and its extensions
Recommended article: A distributed arc-consistency algorithm
Recommended article: A generic arc-consistency algorithm and its specializations
Recommended article: Optimal distributed arc-consistency
Recommended article: Q2767070
Recommended article: Q4424854
description: scientific article; zbMATH DE number 6373257