An O(nlogn)-size fault-tolerant sorting network (extended abstract)
作者： Yuan Ma
关键词:
摘要:
acm.org
sci-hub.se 参考文章(22)
M. Ajtai, J. Komlós, E. Szemerédi, Sorting inc logn parallel steps Combinatorica. ,vol. 3, pp. 1- 19 ,(1983) , 10.1007/BF02579338
Yuan Ma, Fault-tolerant sorting networks Massachusetts Institute of Technology. ,(1995)
R. L. Rivest, A. R. Meyer, D. J. Kleitman, Coping with errors in binary search procedures (Preliminary Report) symposium on the theory of computing. pp. 227- 232 ,(1978) , 10.1145/800133.804351
C. Greg Plaxton, A hypercubic sorting network with nearly logarithmic depth symposium on the theory of computing. pp. 405- 416 ,(1992) , 10.1145/129712.129751
Andrew C Yao, F Frances Yao, None, On fault-tolerant networks for sorting SIAM Journal on Computing. ,vol. 14, pp. 120- 128 ,(1979) , 10.1137/0214009
U. Feige, D. Peleg, P. Raghavan, E. Upfal, Computing with unreliable information symposium on the theory of computing. pp. 128- 137 ,(1990) , 10.1145/100216.100230
Tom Leighton, Yuan Ma, C.Greg Plaxton, Breaking the Θ(nlog2n) Barrier for Sorting with Faults foundations of computer science. ,vol. 54, pp. 265- 304 ,(1997) , 10.1006/JCSS.1997.1470
Jianli Sun, Jan Gecsei, Eduard Cerny, Fault-tolerance in balanced sorting networks Journal of Electronic Testing. ,vol. 1, pp. 31- 41 ,(1990) , 10.1007/BF00134013
Schimmler Manfred, Christoph Starke, A correction network for N -sorters SIAM Journal on Computing. ,vol. 18, pp. 1179- 1187 ,(1989) , 10.1137/0218078
Tom Leighton, Yuan Ma, Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures - SPAA '93. pp. 30- 41 ,(1993) , 10.1145/165231.165235