Sorting networks of logarithmic depth, further simplified

DOI10.1007/S00453-007-9025-6MaRDI QIDQ1024784zbMATH OpenOpenAlexFDO

Authors Joel I. Seiferas

Publication date 17 June 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1802/2610

zbMATH Keywords

analysis of algorithmssorting networkparallel sortingoblivious sortingcomparator networkcomparison network

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Cites work

• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 108570 (Why is no real title available?)
• scientific article; zbMATH DE number 1256707 (Why is no real title available?)
• scientific article; zbMATH DE number 1142304 (Why is no real title available?)
• Construction of halvers
• Improved sorting networks with O(log N) depth
• Introduction to algorithms
• Linear probing and graphs
• Sorting in \(c \log n\) parallel steps

Cited in

(11)

• Expander construction in \(\mathsf{VNC}^1\)
• Bitonic sorters of minimal depth
• Fragile complexity of comparison-based algorithms
• Privacy-preserving group data access via stateless oblivious RAM simulation
• On the complexity of min-max sorting networks
• Improved sorting networks with O(log N) depth
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Fragile complexity of adaptive algorithms
• Expander construction in \(\mathrm{VNC}^1\)
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$
• Fragile complexity of adaptive algorithms

This page was built for publication: Sorting networks of logarithmic depth, further simplified

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