Optimal parallel algorithms for expression tree evaluation and list ranking

Richard Cole, Uzi Vishkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Two related results are presented. The first is a simple n/log n processor, O(log n) time parallel algorithm for list ranking. The second is a general parallel algorithmic technique for computations on trees; it yields the first n/log n processor, O(log n) time deterministic parallel algorithm for expression tree evaluation, and solves many other tree problems within the same complexity bounds.

Original languageEnglish (US)
Title of host publicationVLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings
EditorsJohn H. Reif
PublisherSpringer Verlag
Pages91-100
Number of pages10
ISBN (Print)9780387968186
DOIs
StatePublished - 1988
Event3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988 - Corfu, Greece
Duration: Jun 28 1988Jul 1 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume319 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988
CountryGreece
CityCorfu
Period6/28/887/1/88

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for expression tree evaluation and list ranking'. Together they form a unique fingerprint.

Cite this