Skip to main content
SpringerLink
Log in

Tree-Based Parallel Algorithm Design

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract.

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is complemented by a P-complete tree problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. glmiller@cs.cmu.edu. , , , , , , US

    G. L. Miller

  2. Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, USA. steng@cs.umn.edu. , , , , , , US

    S. -H. Teng

Authors
  1. G. L. Miller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. -H. Teng
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Received February 13, 1995; revised March 25, 1996.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Miller, G., -H. Teng, S. Tree-Based Parallel Algorithm Design. Algorithmica 19, 369–389 (1997). https://doi.org/10.1007/PL00009179

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00009179

Search

Navigation