PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Pinotti M. C., Pucci G. Parallel algorithms for priority queue operations. In: SWAT '92 - Third Scandinavian Workshop on Algorithm Theory. (Helsinki, Finland, July 810 1992). Proceedings, vol. Algorithm Theory SWAT '92 pp. 130 - 139. O. Nurmi, E. Ukkonen (eds.). (Lecture notes in computer science, vol. 621). Springer, 1992.
 
 
Abstract
(English)
This paper presents parallel algorithms for priority queue operations on a p-processor EREW-PRAM. The algorithms are based on a new data structure, the Min-path Heap (MH), which is obtained as an extension of the traditional binary-heap organization. Using an MH, it is shown that insertion of a new item or deletion of the smallest item from a priority queue of n e1ements can be performed in O ( ((log n)) /p + log log n) parallel time, while construction of an MH Crom a set of n items takes O (n/p + log n) time. The given algorithms for insertion and deletion achieve the best possible running time for any number of processors p, with p ⋲ O(log n / ((log log n)) ) while the MH construction algorithm employs up to Θ (n/log n) processors optimally.
Subject Analysis of algorithms
Data structures
Heaps
Parallel algorithms


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional