- View PDF version of TR-91-06 (223885 bytes)
- View PostScript version of TR-91-06
- Save PostScript version of TR-91-06
- Save gzipped PostScript version of TR-91-06 (65334 bytes)

- 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 help@cs.ubc.ca.