A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems
Abstract
In this paper, we propose a parallelized computational scheme called Parallelized Depth-First Algorithm (PDFA) for Branch-and-Bound (B&B) method that works on multiprocessor systems. It is shown theoretically that the space requirement of PDFA on p processing units is at most p times as much as that of the sequential B&B algorithm with the depth-first search function. Moreover, from our experimental results through simulation, it is known that the computation time of PDFA on p processing units can be resuced to less than 1/p that of the sequential B&B algorithm with the depth-first search function. We name this reduction effect in the computation time Acceleration Effect.
Cite
Text
Imai et al. "A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems." International Joint Conference on Artificial Intelligence, 1979.Markdown
[Imai et al. "A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems." International Joint Conference on Artificial Intelligence, 1979.](https://mlanthology.org/ijcai/1979/imai1979ijcai-parallel/)BibTeX
@inproceedings{imai1979ijcai-parallel,
title = {{A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems}},
author = {Imai, Masaharu and Yoshida, Yuuji and Fukumura, Teruo},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1979},
pages = {416-418},
url = {https://mlanthology.org/ijcai/1979/imai1979ijcai-parallel/}
}