The complexity of some polynomial network consistency algorithms for constraint satisfaction problems

Coppersmith, 1982, On the asymptotic complexity of matrix multiplication, SIAM J. Comp., 11, 472, 10.1137/0211038 Freuder, 1978, Synthesizing constraint expressions, Comm. ACM, 21, 958, 10.1145/359642.359654 Freuder, 1982, A sufficient condition for backtrack-free search, J. ACM, 29, 24, 10.1145/322290.322292 Haralick, 1980, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263, 10.1016/0004-3702(80)90051-X Gaschnig, 1979, Performance measurement and analysis of certain search algorithms Mackworth, 1977, Consistency in networks in relations, Artificial Intelligence, 8, 99, 10.1016/0004-3702(77)90007-8 Mackworth, 1977, On reading sketch maps, 598 Montanari, 1974, Networks of constraints: fundamental properties and applications in picture processing, Inform. Sci., 7, 95, 10.1016/0020-0255(74)90008-5 Waltz, 1972, Generating semantic descriptions of scenes with shadows, Tech. Rept., MAC AI-TR-271, MIT