A super-logarithmic lower bound for hypercubic sorting networks

DOI10.1007/3-540-58201-0_103zbMath1422.68092OpenAlexW1512450234MaRDI QIDQ4632461

Torsten Suel, C. Greg Plaxton

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

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

Related Items (2)

A Sorting Network on Trees ⋮ A super-logarithmic lower bound for hypercubic sorting networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved sorting networks with O(log N) depth
• Sorting in \(c \log n\) parallel steps
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• The periodic balanced sorting network
• Theoretical Aspects of VLSI Pin Limitations
• A Lower Bound on the Size of Shellsort Sorting Networks
• A lower bound for sorting networks based on the shuffle permutation
• Hypercubic Sorting Networks
• A super-logarithmic lower bound for hypercubic sorting networks

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