Efficient Parallel Algorithms for Tree Accumulations
Accumulations are higher-order operations on structured objects; they leave the shape of an object unchanged, but replace elements of that object with accumulated information about other elements. Upwards and downwards accumulations on trees are two such operations; they form the basis of many tree...
| Главные авторы: | , , |
|---|---|
| Формат: | Journal article |
| Опубликовано: |
1994
|
| _version_ | 1826304850258821120 |
|---|---|
| author | Gibbons, J Cai, W Skillicorn, D |
| author_facet | Gibbons, J Cai, W Skillicorn, D |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | Accumulations are higher-order operations on structured objects; they leave the shape of an object unchanged, but replace elements of that object with accumulated information about other elements. Upwards and downwards accumulations on trees are two such operations; they form the basis of many tree algorithms. We present two EREW PRAM algorithms for computing accumulations on trees taking O(\\log n) time on O(n/\\log n) processors, which is optimal. |
| first_indexed | 2024-03-07T06:24:00Z |
| format | Journal article |
| id | oxford-uuid:f3a3375e-e92c-4070-93cf-feb8e935ce06 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:24:00Z |
| publishDate | 1994 |
| record_format | dspace |
| spelling | oxford-uuid:f3a3375e-e92c-4070-93cf-feb8e935ce062022-03-27T12:13:41ZEfficient Parallel Algorithms for Tree AccumulationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f3a3375e-e92c-4070-93cf-feb8e935ce06Department of Computer Science1994Gibbons, JCai, WSkillicorn, DAccumulations are higher-order operations on structured objects; they leave the shape of an object unchanged, but replace elements of that object with accumulated information about other elements. Upwards and downwards accumulations on trees are two such operations; they form the basis of many tree algorithms. We present two EREW PRAM algorithms for computing accumulations on trees taking O(\\log n) time on O(n/\\log n) processors, which is optimal. |
| spellingShingle | Gibbons, J Cai, W Skillicorn, D Efficient Parallel Algorithms for Tree Accumulations |
| title | Efficient Parallel Algorithms for Tree Accumulations |
| title_full | Efficient Parallel Algorithms for Tree Accumulations |
| title_fullStr | Efficient Parallel Algorithms for Tree Accumulations |
| title_full_unstemmed | Efficient Parallel Algorithms for Tree Accumulations |
| title_short | Efficient Parallel Algorithms for Tree Accumulations |
| title_sort | efficient parallel algorithms for tree accumulations |
| work_keys_str_mv | AT gibbonsj efficientparallelalgorithmsfortreeaccumulations AT caiw efficientparallelalgorithmsfortreeaccumulations AT skillicornd efficientparallelalgorithmsfortreeaccumulations |