Parallel path consistency

Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, arc consistency is still the preferred technique because it has a much lower time comple...

Full description

Saved in:
Bibliographic Details
Published in:International journal of parallel programming 1991-12, Vol.20 (6), p.453-473
Main Authors: SUSSWEIN, S. Y, HENDERSON, T. C, ZACHARY, J. L, HANSEN, C, HINKER, P, MARSDEN, G. C
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer programming
Computer science
control theory
systems
Exact sciences and technology
Implementations
Information retrieval. Graph
Mathematical models
Parallel processing
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, arc consistency is still the preferred technique because it has a much lower time complexity. Parallel path consistency algorithms are currently being implemented on multiprocessors, and their performance is being compared to the best sequential and parallel arc consistency algorithms. Preliminary work has shown that linear performance increases for parallelized path consistency and that in many cases, performance is significantly better than the theoretical worst case. These two results indicate that parallel path consistency may be a superior filtering technique. Path consistency has been implemented as an outer product computation with good results.
ISSN:0885-7458
1573-7640
DOI:10.1007/BF01547895