The complexity of backtrack searches
L Carter, Larry Stockmeyer, Mark N. Wegman · 1985
In this paper, we study the complexity of finding an efficient search for combinatorial problems which are commonly solved by backtracking. First, a formalism is introduced. Backtrack searches are ordinarily thought of as following a tree pattern. Our model is considerably more general, and there are problems where this allows much shorter searches.