Branch-and-bound and backtrack search on mesh-connected arrays of processors
Christos Kaklamanis, Giuseppe Persiano · 1992
In this paper we investigate the parallel complexity of the backtrack and branch-and-bound search on the mesh-connected array.We present an Q(~/-) lower bound for the time needed by a randomized algorithm to perform backtrack and branch-and-bound search of a tree of depth d on the ~x fl mesh, even when the depth of the tree is known in advance.The lower bound holds also for algorithms that are allowed to move tree-nodes and create multiple copies of the same tre~node.For the upper bounds we give deterministic algorithms that are within a factor of O(log ~N) from our lower bound.Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance and do not move tree-nodes nor create multiple copies of the same node; also, they guarantee optimal load and only need constant-sized buffers.The best previously known algorithm for backtrack search on the mesh was randomized and required O(d@/ log N) time.Our algorithm for branch-andbound is the first algorithm that performs branch-andbound search on a sparae network.Both the lower and the upper bounds extend to higher dimension meshes.