A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
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.
@inproceedings{ijcai1979p90,
title = {A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems},
author = {Imai, Masaharu and Yoshida, Yuuji and Fukumura, Teruo},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/90},
}
TY - CPAPER TI - A Parallel Searching Scheme for Multiprocessor Systems and Its Application to Combinatorial Problems AU - Imai, Masaharu AU - Yoshida, Yuuji AU - Fukumura, Teruo T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/90 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
