TY - GEN
T1 - A parallel branch-and-bound algorithm for MIN-based multiprocessors
AU - Yang, Myung K.
AU - Das, Chita R.
N1 - Funding Information:
lThis research was supported in part by the National Foundation under grant CCR-8810131. Permission to copy without fee all or part of this material granted provided that the copies are not made or distributed for direct commercial advantage, the ACM Ocopyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or speclflc permission. o 1991 ACM 089791 -392 -2/9110005 /0222 ...S1 .5o
Funding Information:
This research was supported in part by the National Science Foundation under grant CCR-8810131.
Publisher Copyright:
© 1991 ACM.
PY - 1991/4/2
Y1 - 1991/4/2
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51649109865&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51649109865&partnerID=8YFLogxK
U2 - 10.1145/107971.108000
DO - 10.1145/107971.108000
M3 - Conference contribution
AN - SCOPUS:51649109865
SN - 0897913922
SN - 9780897913928
T3 - Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991
SP - 222
EP - 223
BT - Proceedings of the 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991
PB - Association for Computing Machinery, Inc
T2 - 1991 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 1991
Y2 - 21 May 1991 through 24 May 1991
ER -