Fast parallel constraint satisfaction

Lefteris M. Kirousis

Research output: Contribution to journalArticlepeer-review


We describe a class of constraint satisfaction problems (CSPs) for which a global solution can be found by a fast parallel algorithm. No relaxation preprocessing is needed for the parallel algorithm to work on this class of CSPs. The result is motivated from the problem of labelling a 2-D line drawing of a 3-D object by the Clowes-Huffman-Malik labelling scheme-an important application of CSP in computer vision. For such a CSP, the constraint graph can be general, but the constraint relations are usually of the type we call implicational. It is shown here that a CSP with this type of constraint relations (and no restrictions on its graph) can be solved by an efficient (i.e., with polynomial time complexity) sequential algorithm. Also, it is shown that it can be solved by a fast parallel algorithm that executes in time O(log3n) with O( (m + n3) logn) processors on an exclusive-read exclusive-write parallel random access machine (n is the number of variables and m is the number of constraint relations-the constraint relations may have arity more than two).

Original languageEnglish (US)
Pages (from-to)147-160
Number of pages14
JournalArtificial Intelligence
Issue number1
StatePublished - Nov 1993

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Fast parallel constraint satisfaction'. Together they form a unique fingerprint.

Cite this