A Time-Randomness Tradeoff for Selection in Parallel
作者： Danny Krizanc
DOI: 10.1007/3-540-57155-8_271
关键词:
摘要: In this paper we study the problem finding median on a parallel comparison tree (PCT). Results due to Valiant [11], Meggido
springer.com
sci-hub.st 参考文章(6)
Nicholas Pippenger, Sorting and selecting in rounds SIAM Journal on Computing. ,vol. 16, pp. 1032- 1038 ,(1987) , 10.1137/0216066
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
Rüdiger Reischuk, Probabilistic Parallel Algorithms for Sorting and Selection SIAM Journal on Computing. ,vol. 14, pp. 396- 409 ,(1985) , 10.1137/0214030
K. Mulmuley, Randomized geometric algorithms and pseudo-random generators Proceedings., 33rd Annual Symposium on Foundations of Computer Science. pp. 90- 100 ,(1992) , 10.1109/SFCS.1992.267815
Leslie G. Valiant, Parallelism in Comparison Problems SIAM Journal on Computing. ,vol. 4, pp. 348- 355 ,(1975) , 10.1137/0204030