A super-logarithmic lower bound for hypercubic sorting networks

DOI10.1007/3-540-58201-0_103MaRDI QIDQ4632461zbMATH OpenOpenAlexFDO

Authors C. Greg Plaxton, Torsten Suel

Publication date 29 April 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58201-0_103

zbMATH Keywords

sorting networkcomparator networkinput patternoutput wirerestricted classis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A superlogarithmic lower bound for shuffle-unshuffle sorting networks
• scientific article; zbMATH DE number 1263220
• Toward a lower bound for sorting networks
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• New Bounds on Optimal Sorting Networks
• Hypercubic Sorting Networks
• A Lower Bound on the Size of Shellsort Sorting Networks
• Bounds to Complexities of Networks for Sorting and for Switching
• A lower bound for sorting networks based on the shuffle permutation
• Lower bounds for sorting on mesh-connected architectures

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1256658 (Why is no real title available?)
• A Lower Bound on the Size of Shellsort Sorting Networks
• A lower bound for sorting networks based on the shuffle permutation
• A super-logarithmic lower bound for hypercubic sorting networks
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Hypercubic Sorting Networks
• Improved sorting networks with O(log N) depth
• Sorting in \(c \log n\) parallel steps
• The periodic balanced sorting network
• Theoretical Aspects of VLSI Pin Limitations

Cited in

(6)

• A sorting network on trees
• A lower bound for sorting networks based on the shuffle permutation
• A super-logarithmic lower bound for hypercubic sorting networks
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• scientific article; zbMATH DE number 5763313 (Why is no real title available?)
• A new upper bound on the queuenumber of hypercubes

This page was built for publication: A super-logarithmic lower bound for hypercubic sorting networks

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