Parallel consistent labeling algorithms

Ashok Samal, Tom Henderson

Research output: Contribution to journalArticle

34 Scopus citations

Abstract

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
Volume16
Issue number5
DOIs
StatePublished - Oct 1987

Keywords

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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

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

  • Cite this