Technical Reports

The ICICS/CS Reading Room

UBC CS TR-91-06 Summary

Parallel and Distributed Algorithms for Constraint Networks", May 1991 Ying Zhang and Alan K. Mackworth, 21 pages

This paper develops two new algorithms for solving a finite constraint satisfaction problem (FCSP) in parallel. In particular, we give a parallel algorithm for the EREW PRAM model and a distributed algorithm for networks of interconnected processors. Both of these algorithms are derived from arc consistency algorithms which are preprocessing algorithms in general, but can be used to solve an FCSP when it is represented by an acyclic constraint network. If an FCSP can be represented by an acyclic constraint network of size \fIn\fP with width bounded by a constant then (1) the parallel algorithm takes \fIO(log n)\fP time using \fIO(n)\fP processors and (2) there is a mapping of this problem to a distributed computing network of \fIpoly(n)\fP processors which stabilizes in \fIO(log n)\fP time.

If you have any questions or comments regarding this page please send mail to