Eugene C. Freuder
Abstract
Backtrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This analysis leads to upper bounds on the effort required for solution of a class of constraint satisfaction problems. The solutions involve a combination of relaxation preprocessing and backtrack search. The bounds are expressed in terms of the structure of the constraint connections. Specifically, the effort is shown to have a bound exponential in the size of the largest biconnected component of the constraint graph, as opposed to the size of the graph as a whole.
- 1 BITNER, J. R., AND REINGOLD, E. M.Backtrack programming techniques. Commun. ACM 18, 11 (Nov. 1975), 651-656. Google Scholar
- 2 BROWN, C. A., AND PURDOM, P. W. JR.,How to search efficiently. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (Vancouver, Canada), 1981, pp. 588-594.Google Scholar
- 3 FIKES, R. E. REF-ARF: A system for solving problems stated as procedures. Artif Intell. 1, 1 (1970), 27-120.Google Scholar
- 4 FREUDER, E.C. Synthesizing constraint expressions. Commun. ACM 2i, ii (Nov. i978), 958- 966. Google Scholar
- 5 FREUDER, E. C. A sufficient condition for backtrack-free search. J. ACM 29, 1 (Jan. 1982), 24- .)Z. Google Scholar
- 6 HARALICK, R. M., AND SHAPIRO, L. G. The consistent labeling problem: Part I. IEEE Trans. Pattern Anal. Machine Intell. PAMI-I. IEEE, New York, 2 (Apr. 1979), pp. 173-184.Google Scholar
- 7 HARALICK, R. M Davis L., Rosenfeld AND Milgram, D Reduction operations fpr constraint l., ............ satisfaction. Inf. Sci. 14 (1978), 199-219.Google Scholar
- 8 KNUTH, D. E.Estimating the efficiency of backtrack programs. Math. Comput. 29 (Jan. 1975), 121-136.Google Scholar
- 9 MACKWORTH, A. K.Consistency in networks of relations. Artif Intell. 8 (1977), 99-118.Google Scholar
- 10 MONTANARI, U.etworks of constraints: Fundamental properties and applications to picture processing. Inf Sei. 7, 2 (Apr. 1974), 95-132.Google Scholar
- 11 REINGOLD, E. M., NIEVERGELT, J., AND DEO, N.Combinatorial Algorithms. Prentice-Hall, Englewood Cliffs, N.J., 1977. Google Scholar
- 12 TARJAN, R. E.Depth-first search and linear graph algorithms. SlAM J. Comput. 1 (1972), 146- 160.Google Scholar
- 13 ULLMAN, J. R.Associating parts of patterns. Inf. Control 9 (1966), 583-601.Google Scholar
- 14 WALTZ, D. L. Understanding line drawings of scenes with shadows. In The Psychology of Computer Vision, P. H. Winston, Ed. Mct_iraw-Hiii, New York, 1975, pp. 19-91.Google Scholar
Index Terms
- A sufficient condition for backtrack-bounded search
Recommendations
Average-case complexity of backtrack search for coloring sparse random graphs
We investigate asymptotically the expected number of steps taken by backtrack search for k-coloring random graphs G"n","p"("n") or proving non-k-colorability, where p(n) is an arbitrary sequence tending to 0, and k is constant. Contrary to the case of ...
A Sufficient Condition for Planar Graphs
A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for ...
Comments