登入
選單
返回
Google圖書搜尋
Optimal Parallel Algorithms for Computing Recursively Defined Functions
Rolf Niedermeier
Peter Rossmanith
出版
SFB
, 1992
URL
http://books.google.com.hk/books?id=8Y42HAAACAAJ&hl=&source=gbs_api
註釋
Abstract: "We investigate recursively defined functions and present optimal algorithms on parallel random access machines (PRAM's) to compute them. It is shown that if for the average width w[bar] of the recursion tree the number of PRAM processors is O(w[bar]/log w[bar]), our parallel algorithms need the same amount of work as the best sequential algorithms for these problems up to a constant factor. In addition, this is possible using the weakest PRAM model, i.e., OROW-PRAM's (owner read, owner write parallel random access machines)."
