The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Richard Cole; Uzi Vishkin

doi:10.1007/BF01762121

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Richard Cole, Uzi Vishkin

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.

Original language	English (US)
Pages (from-to)	329-346
Number of pages	18
Journal	Algorithmica
Volume	3
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01762121
State	Published - Nov 1988

Keywords

Centroid decomposition
Expression tree
List ranking
PRAM
Parallel algorithm

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01762121

Cite this

@article{d84cd0239f384eab88fa59fb2f167ad7,

title = "The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time",

abstract = "A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.",

keywords = "Centroid decomposition, Expression tree, List ranking, PRAM, Parallel algorithm",

author = "Richard Cole and Uzi Vishkin",

year = "1988",

month = nov,

doi = "10.1007/BF01762121",

language = "English (US)",

volume = "3",

pages = "329--346",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

AU - Cole, Richard

AU - Vishkin, Uzi

PY - 1988/11

Y1 - 1988/11

N2 - A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.

AB - A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.

KW - Centroid decomposition

KW - Expression tree

KW - List ranking

KW - PRAM

KW - Parallel algorithm

UR - http://www.scopus.com/inward/record.url?scp=0023863447&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023863447&partnerID=8YFLogxK

U2 - 10.1007/BF01762121

DO - 10.1007/BF01762121

M3 - Article

AN - SCOPUS:0023863447

SN - 0178-4617

VL - 3

SP - 329

EP - 346

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this