Distributed algorithms for selection in sets

DOI10.1016/0022-0000(88)90012-8MaRDI QIDQ1112607zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1390&context=cstech

zbMATH Keywords

ringdistributed algorithmscomplete binary treemeshmessage complexitylinear-time selection algorithmNetwork topologies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• Unifying themes for selection on any network
• scientific article; zbMATH DE number 4050993
• Selection on k-Dimensional Meshes with Multiple Broadcasting
• A distributed selection algorithm and its expected communication complexity
• Fast deterministic selection on mesh-connected processor arrays

Cites work

• scientific article; zbMATH DE number 3763288 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A parallel median algorithm
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Finding the median
• Selection and sorting with limited storage
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Time bounds for selection

Cited in

(11)

• Unifying themes for selection on any network
• Efficient selection and sorting schemes using coteries for processing large distributed files
• Message lower bounds via efficient network synchronization
• Shout echo selection in distributed files
• scientific article; zbMATH DE number 3911705 (Why is no real title available?)
• An improved algorithm for finding the median distributively
• scientific article; zbMATH DE number 4050993 (Why is no real title available?)
• scientific article; zbMATH DE number 4068275 (Why is no real title available?)
• Optimal Distributed Algorithms for Sorting and Ranking
• New algorithms for selection
• A distributed selection algorithm and its expected communication complexity

This page was built for publication: Distributed algorithms for selection in sets

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