Publication Details
Title: Parallel Combinatorial Computing
Author: R. M. Karp
Group: ICSI Technical Reports
Date: January 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-006.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-006
Bibliographic Reference:
R. M. Karp. Parallel Combinatorial Computing. ICSI Technical Report TR-91-006, January 1991
Author: R. M. Karp
Group: ICSI Technical Reports
Date: January 1991
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-91-006.pdf
Overview:
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 Information:
ICSI Technical Report TR-91-006
Bibliographic Reference:
R. M. Karp. Parallel Combinatorial Computing. ICSI Technical Report TR-91-006, January 1991