A minimum-area circuit for \(\ell\)-selection (Q1092661): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: The Area-Time Complexity of Binary Multiplication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A model of computation for VLSI with related complexity results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3711746 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Where-oblivious is not sufficient / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimum Storage Sorting Networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The VLSI Complexity of Sorting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3326832 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3707412 / rank | |||
Normal rank |
Revision as of 12:42, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A minimum-area circuit for \(\ell\)-selection |
scientific article |
Statements
A minimum-area circuit for \(\ell\)-selection (English)
0 references
1987
0 references
We prove tight upper and lower bounds on the area of semelective, when- oblivious VLSI circuits for the problem of \(\ell\)-selection. The area required to select the \(\ell th\) smallest of n k-bit integers is found to be heavily dependent on the relative sizes of \(\ell\), k, and n. When \(\ell <2^ k\), the minimal area is \(A=\theta (\min \{n,\ell (k-\log \ell)\})\). When \(\ell \geq 2^ k\), then \(A=\theta (2^ k(\log \ell - k+1))\).
0 references
area-time complexity
0 references
selection of the \(\ell th\) smallest element
0 references
minimum-area computation
0 references
VLSI algorithms
0 references
lower bounds
0 references
VLSI circuits
0 references
\(\ell \)-selection
0 references