A super-logarithmic lower bound for hypercubic sorting networks

DOI10.1007/3-540-58201-0_103zbMATH Open1422.68092OpenAlexW1512450234MaRDI QIDQ4632461FDOQ4632461

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

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

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)

Cites Work

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

Cited In (6)

• A new upper bound on the queuenumber of hypercubes
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• A Sorting Network on Trees
• Title not available (Why is that?)
• A lower bound for sorting networks based on the shuffle permutation
• A super-logarithmic lower bound for hypercubic sorting networks

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)