IEEE Transactions on Pattern Analysis and Machine Intelligence · 1992 · 24 citations · 18 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureParallel ComputingAlgorithm AnalysisComputational ComplexityConstraint SatisfactionHardware AccelerationParallel Computing SystemsArc ConsistencyParallel Constraint SolvingParallel Time ComplexityPolynomial Time Complexity
The discrete relaxation algorithm (DRA) is a computational technique that enforces arc consistency (AC) in a constraint satisfaction problem (CSP). The original sequential AC-1 algorithm suffers from O(n/sup 3/m/sup 3/) time complexity, and even the optimal sequential AC-4 algorithm is O(n/sup 2/m/sup 2/) for an n-object and m-label DRA problem. Sample problem runs show that these algorithms are all too slow to meet the need for any useful, real-time CSP applications. A parallel DRA5 algorithm that reaches a lower bound of O(nm) (where the number of processors is polynomial in the problem size) is given. A fine-grained, massively parallel hardware computer architecture has been designed for the DRA5 algorithm. For practical problems, many orders of magnitude of efficiency improvement can be reached on such a hardware architecture.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
18
Consistency in networks of relations
Alan K. Mackworth · Artificial Intelligence · 1977 · 2.4K citations