An approach that allows concurrent insertions and deletions on the heap data structure is presented. This scheme has much lower overheads and outperforms previously reported schemes. It also retains the strict priority ordering of the serial-access heap algorithms; i.e., a delete operation returns the best element of all elements that have been inserted or are being inserted. Experimental results on the BBN Butterfly parallel processor demonstrate that the use of concurrent heap algorithms in parallel branch-and-bound improves its performance substantially.
|Original language||English (US)|
|Number of pages||5|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - Dec 1 1988|