Arc consistency: parallelism and domain dependence
Paul R. Cooper, Michael J. Swain · The MIT Press eBooks · 1994
Abstract This paper discusses how better arc consistency algorithms for constraint satisfaction can be developed by exploiting parallelism and domain-specific problem characteristics. A massively parallel algorithm for arc consistency is given, expressed as a digital circuit. For a constraint satisfaction problem with n variables and a labels, this algorithm has a worst-case time complexity of O(na), significantly better than that of the optimal uniprocessor algorithm. An algorithm of intermediate parallelism suitable for implementation on a SIMD machine is also given. Analyses and implementation experiments are shown for both algorithms. A method for exploiting characteristics of a problem domain to achieve arc consistency algorithms with better time and space complexity is also discussed. A general technique for expressing domain knowledge and using it to develop optimized arc consistency algorithms is described. The domain-specific optimizations can be applied analogously to any of the arc consistency algorithms along the sequential/parallel spectrum.