A lower bound for sorting networks based on the shuffle permutation

DOI10.1007/BF01184936zbMATH Open0812.68069OpenAlexW4250527476MaRDI QIDQ4311642FDOQ4311642

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

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

zbMATH Keywords

sorting network

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting in \(c \log n\) parallel steps
• Rearrangeability of multistage shuffle/exchange networks
• Notes on Shuffle/Exchange-Type Switching Networks
• Interpolation between bases and the shuffle exchange network
• Improved sorting networks with O(log N) depth
• A Lower Bound on the Size of Shellsort Sorting Networks
• A unified theory of interconnection network structure
• Theoretical Aspects of VLSI Pin Limitations
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• A quadratic lower bound for topswops
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• A Lower Bound on the Size of Shellsort Sorting Networks
• Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
• A super-logarithmic lower bound for hypercubic sorting networks
• Optimal parallel selection in sorted matrices

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)