Hypercubic Sorting Networks

DOI10.1137/S0097539794268406MaRDI QIDQ4388861zbMATH OpenOpenAlexFDO

Authors Tom Leighton, C. Greg Plaxton

Publication date 10 May 1998

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

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

zbMATH Keywords

hypercubic machinesparallel sortingsorting networks

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Recommendations

• A super-logarithmic lower bound for hypercubic sorting networks
• Sorting in rounds
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Cubesort: A parallel algorithm for sorting N data items with S-sorters

Cited in

(7)

• Sorting-based selection algorithms for hypercubic networks
• On partial sorting in restricted rounds
• Majority Bootstrap Percolation on the Hypercube
• A super-logarithmic lower bound for hypercubic sorting networks
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• A sorting network on trees
• Privacy-preserving group data access via stateless oblivious RAM simulation

This page was built for publication: Hypercubic Sorting Networks

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