Towards better algorithms for parallel backtracking

Many algorithms in operations research and artificial intelligence
are based on depth first search in implicitly defined trees.
For parallelizing these algorithms, a load balancing scheme is
needed which is able to evenly distribute parts of an irregularly
shaped tree over the processors. It should work with minimal
interprocessor communication and without prior knowledge of the
tree's shape.

Previously known load balancing algorithms either require sending a
message for each tree node or they only work efficiently for large
search trees. This paper introduces new randomized dynamic load
balancing algorithms for {\em tree structured computations}, a
generalization of backtrack search.These algorithms only need to
communicate when necessary and have an asymptotically optimal
scalability for many important cases.
They work work on hypercubes, butterflies, meshes and many other
architectures.