A New Algorithm for Maintaining Arc Consistency After Constraint Retraction

摘要

Dynamic Constraint Satisfaction Problems play a very important role in modeling and solving real-life problems where the set of constraints is changing. The paper addresses a problem of maintaining arc consistency after removing a constraint from the constraint model. A new dynamic arc consistency algorithm is proposed that improves the practical time efficiency of the existing AC|DC algorithm by using additional data-structures. The algorithm achieves real time efficiency close to the so far fastest DynAC-6 algorithm while keeping the memory consumption low.