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 CREW PRAM algorithm has been given 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. A modified algorithm is presented which 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). |
Year | DOI | Venue |
---|---|---|
1990 | 10.1109/SPDP.1990.143590 | Dallas, TX |
Keywords | DocType | ISBN |
parallel dynamic programming,modified algorithm,crew pram algorithm,processor requirement,optimal triangulation,optimal order,optimal binary search tree,matrix multiplication,dynamic programming problem,log n,time complexity,binary search trees,computational complexity,open systems,dynamic programming,computer science,polygons,parallel algorithms,binary trees,triangulation,binary search tree | Conference | 0-8186-2087-0 |
Citations | PageRank | References |
5 | 0.55 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Viswanathan, V. | 1 | 5 | 0.55 |
Shou-hsuan Stephen Huang | 2 | 174 | 59.88 |
Hongfei Liu | 3 | 21 | 4.36 |