Space-efficient parallel algorithms for combinatorial search problems

• Backtrack Search: quasi-optimal parallel algorithm and an optimal Las Vegas randomized one.
• Branch-and-bound: Las Vegas randomized parallel algorithm achieving sublinear running time.
• All algorithms require constant space per processor, unlike previous algorithms in the literature.

We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound  , both involving the visit of an nn-node tree of height hh under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a pp-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in O(n/p+hlogp)O(n/p+hlogp) time, and a Las Vegas algorithm requiring optimal O(n/p+h)O(n/p+h) time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in O((n/p+hlogplogn)hlog2n)O((n/p+hlogplogn)hlog2n) time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored.