ML Anthology

Node and Arc Consistency in Weighted CSP

Javier Larrosa
AAAI 2002 pp. 48-53
doi:10.5555/777092.777103 /aaai/2002/larrosa2002aaai-node/

Abstract

Recently, a general definition of arc consistency (AC) for soft constraint frameworks has been proposed (Schiex 2000). In this paper we specialize this definition to weighted CSP and introduce a O(ed3) algorithm. Then, We refine the definition and introduce a stronger form of arc consistency (AC*) along with a O(n2d3) algorithm. We empirically demonstrate that AC* is likely to be much better than AC in terms of pruned values.

PDF AAAI Semantic Scholar

Cite

Text

Larrosa. "Node and Arc Consistency in Weighted CSP." AAAI Conference on Artificial Intelligence, 2002. doi:10.5555/777092.777103

Markdown

[Larrosa. "Node and Arc Consistency in Weighted CSP." AAAI Conference on Artificial Intelligence, 2002.](https://mlanthology.org/aaai/2002/larrosa2002aaai-node/) doi:10.5555/777092.777103

BibTeX

@inproceedings{larrosa2002aaai-node,
  title     = {{Node and Arc Consistency in Weighted CSP}},
  author    = {Larrosa, Javier},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2002},
  pages     = {48-53},
  doi       = {10.5555/777092.777103},
  url       = {https://mlanthology.org/aaai/2002/larrosa2002aaai-node/}
}