Bit complexity of order statistics on a distributed star network

DOI10.1016/0020-0190(89)90130-0MaRDI QIDQ1116337zbMATH OpenOpenAlexFDO

Authors Ornan Gerstel, Yishay Mansour, Shmuel Zaks

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90130-0

zbMATH Keywords

selectionrankingorder statisticslower boundsortingbit complexityasynchronous distributed star network

Mathematics Subject Classification ID

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

Recommendations

• The bit complexity of distributed sorting
• Order preserving communication on a star network
• Two absolute bounds for distributed bit complexity
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 962463
• Distributed computation of exact average degree and network size in finite time under quantized communication
• On randomized broadcasting in star graphs
• Graph-Theoretic Concepts in Computer Science
• Lower bounds on communication complexity in distributed computer networks
• An optimal bit complexity randomized distributed MIS algorithm

Cites work

• scientific article; zbMATH DE number 3800917 (Why is no real title available?)
• Distributed Sorting
• Optimal Distributed Algorithms for Sorting and Ranking
• The bit complexity of distributed sorting
• The complexity of sorting on distributed systems

Cited in

(1)

• scientific article; zbMATH DE number 4068275 (Why is no real title available?)

This page was built for publication: Bit complexity of order statistics on a distributed star network

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