Parallel dynamic programming
Shou‐Hsuan Stephen Huang, Hongfei Liu, Venkatraman Viswanathan · IEEE Transactions on Parallel and Distributed Systems · 1994
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(n/sup 6//log n) processors and runs in O(log/sup 2/ n) time. In this article, a modified algorithm is presented that reduces the processor requirement to O(n/sup 6//log /sup 5/n) while maintaining the same time complexity of O(log/sup 2/ n).>