# Alan K. Mackworth's Publications

•
Sorted by Date •
Classified by Publication Type •
Sorted by First Author Last Name •
Classified by Author Last Name •

## Parallel and Distributed Algorithms for Finite Constraint Satisfaction Problems

Y. Zhang and Alan K. Mackworth. Parallel and Distributed Algorithms for Finite Constraint
Satisfaction Problems. In *Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing*, pp. 394–397,
Dallas, TX, December 1991.

### Download

[PDF]381.1kB

### Abstract

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. If an FCSP
can be represented by an acyclic constraint network of
size n with width bounded by a constant then (1) the
parallel algorithm takes O(1ogn) time using O(n) processors
and (2) there is a mapping of this problem to
a distributed computing network of poly(n) processors
which stabilizes in O(1ogn) time.

### BibTeX

@InProceedings{IEEE-PDP91,
author = {Y. Zhang and Alan K. Mackworth},
title = {Parallel and Distributed Algorithms for Finite Constraint Satisfaction Problems},
year = {1991},
month = {December},
booktitle = {Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing},
address = {Dallas, TX}
pages = {394--397},
abstract = { 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. If an FCSP
can be represented by an acyclic constraint network of
size n with width bounded by a constant then (1) the
parallel algorithm takes O(1ogn) time using O(n) processors
and (2) there is a mapping of this problem to
a distributed computing network of poly(n) processors
which stabilizes in O(1ogn) time. },
bib2html_pubtype ={Refereed Conference Proceeding},
bib2html_rescat ={},
}

Generated by
bib2html.pl
(written by Patrick Riley
) on
Wed Apr 23, 2014 19:08:34