Title :
Parallel and distributed algorithms for finite constraint satisfaction problems
Author :
Zhang, Ying ; Mackworth, Alan K.
Author_Institution :
Dept. of Comput. Sci., British Columbia Univ., Vancouver, BC, Canada
Abstract :
The authors develop two new algorithms for solving a finite constraint satisfaction problem (FCSP) in parallel. In particular, they give a parallel algorithm for the EREW PRAM model and a distributed algorithm for networks of interconnected processors. If an FCSP can be represented by an acyclic constraint network of size n with width bounded by a constant then: the parallel algorithm takes O(log n) time using O(n) processors and there is a mapping of this problem to a distributed computing network of poly(n) processors which stabilizes in O(log n) time
Keywords :
computational complexity; constraint theory; distributed algorithms; multiprocessor interconnection networks; parallel algorithms; EREW PRAM; acyclic constraint network; distributed algorithms; distributed computing network; finite constraint satisfaction problems; interconnected processors networks; parallel algorithm; Computer science; Distributed algorithms; Distributed computing; Image databases; Image retrieval; Information retrieval; Parallel algorithms; Phase change random access memory;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218214
