Parallel dynamic programming |
| |
| Authors: | Huang S-HS Hongfei Liu Viswanathan V |
| |
| Affiliation: | Dept. of Comput. Sci., Houston Univ., TX; |
| |
| Abstract: | Recurrence formulations for various problems, such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangulation of polygons, assume a similar form. A. Gibbons and W. Rytter (1988) gave a CREW PRAM algorithm to solve such dynamic programming problems. The algorithm uses O(n6/log n) processors and runs in O(log2 n) time. In this article, a modified algorithm is presented that reduces the processor requirement to O(n6/log 5n) while maintaining the same time complexity of O(log2 n) |
| |
| Keywords: | |
|
|
