EFFICIENT PARALLEL ALGORITHMS FOR TRE 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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
1994
|
| _version_ | 1826261660799598592 |
|---|---|
| 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. © 1994. |
| first_indexed | 2024-03-06T19:24:51Z |
| format | Journal article |
| id | oxford-uuid:1b5b5825-502e-4ec9-b220-28e65906ee44 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:24:51Z |
| publishDate | 1994 |
| record_format | dspace |
| spelling | oxford-uuid:1b5b5825-502e-4ec9-b220-28e65906ee442022-03-26T10:59:57ZEFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONSJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1b5b5825-502e-4ec9-b220-28e65906ee44EnglishSymplectic Elements at Oxford1994Gibbons, 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. © 1994. |
| spellingShingle | Gibbons, J Cai, W Skillicorn, D EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title | EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title_full | EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title_fullStr | EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title_full_unstemmed | EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title_short | EFFICIENT PARALLEL ALGORITHMS FOR TRE ACCUMULATIONS |
| title_sort | efficient parallel algorithms for tre accumulations |
| work_keys_str_mv | AT gibbonsj efficientparallelalgorithmsfortreaccumulations AT caiw efficientparallelalgorithmsfortreaccumulations AT skillicornd efficientparallelalgorithmsfortreaccumulations |