Bounds on Selection Networks

DOI10.1137/0209043MaRDI QIDQ3890124zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao

Publication date 1980

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0209043

zbMATH Keywords

comparatorscomplexity of network selectiondelay timesorting network

Mathematics Subject Classification ID

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

Cited in

(5)

• On the complexity of monotone circuits for threshold symmetric Boolean functions
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$
• Towards simpler sorting networks and monotone circuits for majority
• Revisiting oblivious top-k selection with applications to secure k-NN classification
• Accelerating certain outputs of merging and sorting networks

This page was built for publication: Bounds on Selection Networks

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