摘要: We present upper bounds for sorting and selecting the median in a fixed number of rounds. These match known lower to within logarithmic factors. They also have merit being “explicit modulo expansion”; that is, probabilistic arguments are used only obtain expanding graphs, when explicit constructions such graphs found, algorithms will follow. Using best currently available we
core.ac.uk
sci-hub.se 参考文章(4)
A Lubotzky, R Phillips, P Sarnak, Explicit expanders and the Ramanujan conjectures symposium on the theory of computing. pp. 240- 246 ,(1986) , 10.1145/12130.12154
R. Häggkvist, P. Hell, Sorting and Merging in Rounds Siam Journal on Algebraic and Discrete Methods. ,vol. 3, pp. 465- 473 ,(1982) , 10.1137/0603047
Kruskal, Searching, Merging, and Sorting in Parallel Computation IEEE Transactions on Computers. ,vol. 32, pp. 942- 946 ,(1983) , 10.1109/TC.1983.1676138
A. Borodin, J.E. Hopcroft, Routing, merging, and sorting on parallel models of computation Journal of Computer and System Sciences. ,vol. 30, pp. 130- 145 ,(1985) , 10.1016/0022-0000(85)90008-X