Accession Number:

ADA172445

Title:

The Complexity of Parallel Algorithms,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Anderson, Richard

Report Date:

1985-11-01

Pagination or Media Count:

72.0

Abstract:

This thesis addresses a number of theoretical issues in parallel computation. There are many open questions relating to what can be done with parallel computers and what are the most effective techniques to use to develop parallel algorithms. The author examines various problems in hope of gaining insight to the general questions. One topic that is investigated is the relationship between sequential and parallel algorithms. Introduced is the concept of a P-complete algorithm to capture what it means for an algorithm to be inherently sequential . It is shown that a number of sequential greedy algorithms are P-complete, including the greedy algorithm for finding a path in a graph. However, a problem is not necessarily difficult if an algorithm to solve it is P-complete. In some cases, the natural sequential algorithm is P-complete but a different technique gives a fast parallel algorithm. This shows that it is necessary to use different techniques for parallel computation than are used for sequential computation. Fast parallel algorithms for a number of simple graph theory problems are given. The algorithms illustrate a number of different techniques that are useful for parallel algorithms. The final topic that we address is parallel approximation of P-complete problems.

Descriptors:

• *ALGORITHMS
• *PARALLEL PROCESSING
• COMPUTATIONS
• GRAPHS
• THEORY
• SEQUENCES
• PROBLEM SOLVING

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE