A survey of randomness and parallelism in comparison problems
作者： Danny Krizanc
DOI: 10.1007/3-540-64359-1_703
关键词:
摘要: A survey of results for the problems selection, merging and sorting in Randomized Parallel Comparison Tree (RPCT) model is given. The indicate that while randomization “helps” case it does not provide any advantage cases sorting, this model.
springer.com
sci-hub.st 参考文章(37)
N. Alon, Y. Azar, The average complexity of deterministic and randomized parallel comparison-sorting algorithms SIAM Journal on Computing. ,vol. 17, pp. 1178- 1192 ,(1988) , 10.1137/0217074
Y. Azar, Parallel comparison merging of many-ordered lists Theoretical Computer Science. ,vol. 83, pp. 275- 285 ,(1991) , 10.1016/0304-3975(91)90279-B
Howard Karloff, Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers symposium on the theory of computing. pp. 310- 321 ,(1988) , 10.1145/62212.62242
Danny Krizanc, David Peleg, Eli Upfal, A time-randomness tradeoff for oblivious routing symposium on the theory of computing. pp. 93- 102 ,(1988) , 10.1145/62212.62221
Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 222- 227 ,(1977) , 10.1109/SFCS.1977.24
Uzi Vishkin, Yossi Azar, Tight Comparison Bounds on the Complexity of Parallel Sorting ,(2018)
Kruskal, Searching, Merging, and Sorting in Parallel Computation IEEE Transactions on Computers. ,vol. 32, pp. 942- 946 ,(1983) , 10.1109/TC.1983.1676138
Rüdiger Reischuk, Probabilistic Parallel Algorithms for Sorting and Selection SIAM Journal on Computing. ,vol. 14, pp. 396- 409 ,(1985) , 10.1137/0214030
D. Krizanc, L. Narayanan, R. Raman, Fast deterministic selection on mesh-connected processor arrays Algorithmica. ,vol. 15, pp. 319- 331 ,(1996) , 10.1007/BF01961542
Christos Kaklamanis, Danny Krizanc, Lata Narayanan, Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version) Proceedings of the third annual ACM symposium on Parallel algorithms and architectures - SPAA '91. pp. 17- 28 ,(1991) , 10.1145/113379.113381