A lower bound for sorting networks based on the shuffle permutation

DOI10.1007/BF01184936MaRDI QIDQ4311642zbMATH OpenOpenAlexFDO

Authors C. Greg Plaxton, Torsten Suel

Publication date 30 October 1994

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01184936

zbMATH Keywords

sorting network

Mathematics Subject Classification ID

Searching and sorting (68P10) Network design and communication in computer systems (68M10)

Recommendations

• A superlogarithmic lower bound for shuffle-unshuffle sorting networks
• scientific article; zbMATH DE number 1263220
• Optimal-depth sorting networks
• A super-logarithmic lower bound for hypercubic sorting networks
• A Lower Bound on the Size of Shellsort Sorting Networks

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1256658 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Lower Bound on the Size of Shellsort Sorting Networks
• A unified theory of interconnection network structure
• Improved sorting networks with O(log N) depth
• Interpolation between bases and the shuffle exchange network
• Notes on Shuffle/Exchange-Type Switching Networks
• Rearrangeability of multistage shuffle/exchange networks
• Sorting in \(c \log n\) parallel steps
• Theoretical Aspects of VLSI Pin Limitations

Cited in

(7)

• scientific article; zbMATH DE number 403954 (Why is no real title available?)
• A super-logarithmic lower bound for hypercubic sorting networks
• A quadratic lower bound for topswops
• Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
• Optimal parallel selection in sorted matrices
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• A Lower Bound on the Size of Shellsort Sorting Networks

This page was built for publication: A lower bound for sorting networks based on the shuffle permutation

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