Concurrent insertions and deletions in a priority queue

Rao V. Nageshwara, Vipin Kumar

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)207-211
Number of pages5
JournalProceedings of the International Conference on Parallel Processing
Volume3
StatePublished - Dec 1 1988

Fingerprint Dive into the research topics of 'Concurrent insertions and deletions in a priority queue'. Together they form a unique fingerprint.

Cite this