The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time |
| |
| Authors: | Richard Cole and Uzi Vishkin |
| |
| Affiliation: | (1) Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(2) Computer Science Department, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel |
| |
| Abstract: | A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities. |
| |
| Keywords: | Expression tree Parallel algorithm PRAM Centroid decomposition List ranking |
| 本文献已被 SpringerLink 等数据库收录！ |
|
