A parallel branch-and-bound algorithm for MIN-based multiprocessors
Myung K. Yang, Chita R. Das · 1991
A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.