Name
Abstract | ||
|---|---|---|
In this brief contribution, we present a constant time sorting algorithm by adopting a 3-D reconfigurable mesh with only O(n3/2) processors. Our algorithm is developed on an n1/2 x n1/2 x n1/2 3-D reconfigurable mesh. Moreover, we further extend the result to k-dimensional reconfigurable meshes for k greater-than-or-equal-to 3. Consequently, an O(4k+1) time sorting algorithm is obtained by adopting an n1/(k-1) x n1/(k-1) x ... x n1/(k-1)k-dimensional reconfigurable mesh of size O(n1+1/(k-1)). Hence, constant time sorting using O(n1+epsilon) processors, where O < epsilon much less than 1, can he realized by adopting reconfigurable meshes of high dimensions. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1109/12.286307 | IEEE Trans. Computers |
Keywords | Field | DocType |
computer science,information technology,parallel algorithms,sorting,parallel algorithm,sorting algorithm,broadcasting,computational complexity,telecommunications | Reconfigurable mesh,Polygon mesh,Computer science,Parallel algorithm,Parallel computing,Real-time computing,Sorting,Sorting algorithm,Control reconfiguration,Computational complexity theory | Journal |
Volume | Issue | ISSN |
43 | 6 | 0018-9340 |
Citations | PageRank | References |
12 | 0.68 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yen-Cheng Chen | 1 | 152 | 15.38 |
| Wen-Tsuen Chen | 2 | 1271 | 129.24 |