Improved sorting networks with O(log N) depth
From MaRDI portal
Publication:582098
DOI10.1007/BF01840378zbMath0689.68066OpenAlexW2034955722WikidataQ56337888 ScholiaQ56337888MaRDI QIDQ582098
Publication date: 1990
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840378
Related Items (25)
Expander Construction in VNC1 ⋮ Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes ⋮ Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults ⋮ Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Real-time emulations of bounded-degree networks ⋮ A lower bound for sorting networks based on the shuffle permutation ⋮ On (Valiant’s) Polynomial-Size Monotone Formula for Majority ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Combinatorial search in two and more rounds ⋮ A sorting network in bounded arithmetic ⋮ On the complexity of min-max sorting networks ⋮ Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons ⋮ A super-logarithmic lower bound for hypercubic sorting networks ⋮ Picture-hanging puzzles ⋮ Improved fault-tolerance sorting algorithm in hypercubes ⋮ Fragile complexity of adaptive algorithms ⋮ Fragile complexity of comparison-based algorithms ⋮ Smallest compact formulation for the permutahedron ⋮ Fragile complexity of adaptive algorithms ⋮ Sorting networks of logarithmic depth, further simplified ⋮ Boolean circuit programming: A new paradigm to design parallel algorithms ⋮ Periodic comparator networks ⋮ Unnamed Item ⋮ Construction of halvers
Cites Work
This page was built for publication: Improved sorting networks with O(log N) depth
