Arc-Consistency for Temporal Constraint Satisfaction Problems
A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms
We define a notion of arc-consistency for temporal constraints, which we will refer to as binarized-domains arc-consistency, or bdarc-consistency for short.We show that if a convex temporal constraint satisfaction problem, referred to in [dechter et al.We provide an algorithm achieving bdarc-consistency for a convex temporal constraint satisfaction problem, which we will refer to as bdac-3, for it is an adaptation of mackworth s [1977] well-known arc-consistency algorithm ac-3.From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an ir-labelled directed graph.
