Parallel Combinatorial Computing

TitleParallel Combinatorial Computing
Publication TypeTechnical Report
Year of Publication1991
AuthorsKarp, R. M.
Other Numbers636

In this article we suggest that the application of highly parallel computers to applications with a combinatorial or logical flavor will grow in importance. We briefly survey the work of theoretical computer scientists on the construction of efficient parallel algorithms for basic combinatorial problems. We then discuss a two-stage algorithm design methodology, in which an algorithm is first designed to run on a PRAM and then implemented for a distributed-memory machine. Finally, we propose the class of node expansion algorithms as a fruitful domain for the application of highly parallel computers.

Bibliographic Notes

ICSI Technical Report TR-91-006

Abbreviated Authors

R. M. Karp

ICSI Publication Type

Technical Report