A distributed selection algorithm and its expected communication complexity

DOI10.1016/0304-3975(92)90368-PzbMath0780.68006MaRDI QIDQ1193632

Jeffrey B. Sidney, Stuart J. Sidney, Nicola Santoro

Publication date: 27 September 1992

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

zbMATH Keywords

worst-case complexitydistributed \(K\)-selection problemdistributed selectionexpected communication complexitypoint-to-point model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Related Items (3)

EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES ⋮ The Complexity of Data Aggregation in Directed Networks ⋮ Distributed and Robust Support Vector Machine

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved algorithm for finding the median distributively
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Distributed Sorting
• Optimal Distributed Algorithms for Sorting and Ranking
• Shout echo selection in distributed files
• Lower Bounds on Information Transfer in Distributed Computations

This page was built for publication: A distributed selection algorithm and its expected communication complexity