Bounds to Complexities of Networks for Sorting and for Switching
From MaRDI portal
Publication:4101728
DOI10.1145/321879.321882zbMath0334.94007OpenAlexW2005874499MaRDI QIDQ4101728
David E. Muller, Franco P. Preparata
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2142/74770
Formal languages and automata (68Q45) Switching theory, applications of Boolean algebras to circuits and networks (94C11)
Related Items
An introduction to parallelism in combinatorial optimization, A VLSI algorithm for sorting variable-length character strings, Fast integer merging on the EREW PRAM, EFFICIENT HARDWARE ALGORITHMS FOR N CHOOSE K COUNTERS USING THE BITONIC MERGER, Fast Pseudorandom Functions Based on Expander Graphs, Some parallel algorithms on interval graphs, A simple nc recognition algorithm for welsh-powell opposition graphs, Parallel circle-cover algorithms, A unified \(O(\log N)\) and optimal sorting vector algorithm, A parallel sorting scheme whose basic operation sortsN elements, Some subclasses of context-free languages in \(NC^ 1\), Efficient monotone circuits for threshold functions, Upper bounds on the multiplicative complexity of symmetric Boolean functions, Integer summing algorithms on reconfigurable meshes, ERCW PRAMs and optical communication, Two-way automata and length-preserving homomorphisms, The complexity of contract negotiation, Linear-size constant-depth polylog-threshold circuits, On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\)., Parallel restructuring and evaluation of expressions, The complexity of computing symmetric functions using threshold circuits, Parallel algorithms on circular-arc graphs, FM SCREENING BY THE LOCAL EXHAUSTIVE SEARCH, WITH HARDWARE ACCELERATION, On the combinational complexity of certain symmetric Boolean functions, Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case, Parallel Generation of ℓ-Sequences, A NEW FM SCREENING METHOD TO GENERATE CLUSTER-DOT BINARY IMAGES USING THE LOCAL EXHAUSTIVE SEARCH WITH FPGA ACCELERATION, Exact learning of DNF formulas using DNF hypotheses, On the depth complexity of formulas, Some classes of languages in \(NC^ 1\), A new parallel sorting algorithm based upon min-mid-max operations, New lower bound techniques for VLSI, Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
