Propagation Methods
Propagation methods were the backbone of many of the early constraint solving
systems. In this method, the constraints are first translated into a system
of equations involving variables and constants. An undirected graph is
then created which has the equations, the variables, and the constants as
nodes, and an edge between two nodes indicates that a variable or constant
appears in an equation. The goal then is to transform the graph into a
directed graph so that all the equations can solved beginning with the
constants. Various propagation methods have been used in an attempt to
reach this goal, but none of them guarantees that a solution will be
derived, nor do they have a reasonable worst-case running time. For a
review of these methods, see [97].
References
- A. H. Borning [5]
- Brown Associates, Inc. [9]
- B. N. Freeman-Benson, J. Maloney, and A. Borning [31]
- T. W. Fuqua [34]
- J. Gosling [36]
- J. Li [65]
- G. L. Steele and G. L. Sussman [100]
- I. Sutherland [105]
- M. R. Wilk [117]
