Architecture independent parallel selection with applications to parallel priority queues

DOI10.1016/S0304-3975(02)00572-8MaRDI QIDQ1399984zbMATH OpenOpenAlexFDO

Authors A. V. Gerbessiotis, C. J. Siniolakis

Publication date 30 July 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00572-8

zbMATH Keywords

algorithmsselectionBSP modelpriority queuesHeaps

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Randomized priority queues for fast parallel access
• The bulk-synchronous parallel random access machine
• Probabilistic Parallel Algorithms for Sorting and Selection
• scientific article; zbMATH DE number 2099204
• scientific article; zbMATH DE number 1760034

Cites work

• scientific article; zbMATH DE number 4213428 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1142307 (Why is no real title available?)
• scientific article; zbMATH DE number 1760034 (Why is no real title available?)
• A Unified Lower Bound for Selection and Set Partitioning Problems
• Architecture independent parallel algorithm design: theory vs practice
• Average case selection
• Bounds for Selection
• Concurrent access of priority queues
• Expected time bounds for selection
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Finding the median
• Median selection requires \((2+\varepsilon)n\) comparisons
• Ordered \(h\)-level graphs on the BSP model
• Parallel heap: an optimal parallel priority queue
• Parallel permutation and sorting algorithms and a new generalized connection network
• Parallel priority queues
• Practical considerations of parallel simulations and architecture independent parallel algorithm design
• Priority queues on parallel machines
• Probabilistic Parallel Algorithms for Sorting and Selection
• Randomized parallel algorithms for backtrack search and branch-and-bound computation
• Selecting the Median
• Time bounds for selection

Cited in

(7)

• Coarse grained parallel selection
• Priority queues on parallel machines
• An architecture independent study of parallel segment trees
• A randomized sorting algorithm on the BSP model
• scientific article; zbMATH DE number 2099204 (Why is no real title available?)
• scientific article; zbMATH DE number 1760034 (Why is no real title available?)
• Portable and architecture independent parallel performance tuning using BSP.

This page was built for publication: Architecture independent parallel selection with applications to parallel priority queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399984)