Parallel consistent labeling algorithms

Ashok Samal, Tom Henderson

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.(1) Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.(2) In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, where n is number of nodes, and a is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.

Original languageEnglish (US)
Pages (from-to)341-364
Number of pages24
JournalInternational Journal of Parallel Programming
Issue number5
StatePublished - Oct 1987
Externally publishedYes


  • Arc consistency
  • constraint satisfaction
  • inherent parallelism
  • parallel algorithms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'Parallel consistent labeling algorithms'. Together they form a unique fingerprint.

Cite this