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

Richard Cole, Uzi Vishkin

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)329-346
Number of pages18
JournalAlgorithmica
Volume3
Issue number1
DOIs
StatePublished - Mar 1988

Keywords

  • Centroid decomposition
  • Expression tree
  • List ranking
  • PRAM
  • Parallel algorithm

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time'. Together they form a unique fingerprint.

Cite this