A Caltech Library Service

Best-first branch-and-bound on a hypercube

Felten, Edward W. (1988) Best-first branch-and-bound on a hypercube. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 1500-1504. ISBN 0-89791-278-0.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The branch-and-bound technique is a common method for finding exact solutions to difficult problems in combinatorial optimization. This paper will discusss issues surrounding implementation of a particular branch-and-bound algorithm for the traveling-salesman problem on a hypercube multicomputer. The natural parallel algorithm is based on a number of asynchronous processes which interact through a globally shared list of unfinished work. In a distributed-memory environment, we must find a non-centralized version of this shared data structure. In addition, detecting termination of the computation is tricky; an algorithm will be presented which ensures proper termination. Finally, issues affecting performance will be discussed.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1988 ACM.
Record Number:CaltechAUTHORS:20161013-134329569
Persistent URL:
Official Citation:E. W. Felten. 1989. Best-first branch-and bound on a hypercube. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1500-1504. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71064
Deposited By: Kristin Buxton
Deposited On:13 Oct 2016 21:03
Last Modified:11 Nov 2021 04:39

Repository Staff Only: item control page