MUSE CSP (Multiply SEgmented Constraint Satisfaction Problem) [5, 61 is an extension to the constraint satisfaction problem (CSP) which is especially useful for problems that segment into riultiple instances of CSP that share variables. In Belzerman and Harper [6], the concepts of MUSE node, arc, and path consistency were defined and algorithms for MUSE arc consistency, MUSE AC-1, and MUSE path consistency were developed. MUSE AC-1 is similar to the CSP arc consistency algorithm AC-4 [ l j ] . Recently, Bessikre developed a new algorithm, AC-6 [I], which has the same worst-case running time as AC-4 and is faster than AC-3 and AC-4 in practice. In this paper, we focus on developing two faster MUSE arc consistency algor~thms:M USE AC-2 which directly applies Bessikre's method to improve upon MUSE AC-1, and MUSE AC-3, which uses our new "lazy" evaluation method for keeping track of the additional sets required by the MUSE approach. These new algorithms decrease the number of steps required to achieve arc ccnsistency in randomly generated MUSE CSP instances when compared to MUSE AC-1. Keyvrords: Problem Solving, Constraint Satisfaction, MUSE arc consistency.

Date of this Version

December 1997