Parallel Hardware for Constraint Satisfaction
Abstract
A parallel implementation of constraint satisfaction by arc consistency is presented. The implementation is constructed of standard digital hardware elements, used in a very fine-grained, massively parallel style. As an example of how to specialize the design, a parallel implementation for solving graph isomorphism with arc consistency is also given. Complexity analyses are given for both circuits. Worst case running time for the algorithms turns out to be linear in the number of variables n and labels a, O(an), and if the I/O must be serial, it will dominate the computation time. Finegrained parallelism trades off time complexity for space complexity, but the number of gates required is only O(a2n2).
Cite
Text
Swain and Cooper. "Parallel Hardware for Constraint Satisfaction." AAAI Conference on Artificial Intelligence, 1988.Markdown
[Swain and Cooper. "Parallel Hardware for Constraint Satisfaction." AAAI Conference on Artificial Intelligence, 1988.](https://mlanthology.org/aaai/1988/swain1988aaai-parallel/)BibTeX
@inproceedings{swain1988aaai-parallel,
title = {{Parallel Hardware for Constraint Satisfaction}},
author = {Swain, Michael J. and Cooper, Paul R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1988},
pages = {682-686},
url = {https://mlanthology.org/aaai/1988/swain1988aaai-parallel/}
}