Parallel dynamic programming

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 us...

Full description

Saved in:
Bibliographic Details
Main Authors: Viswanathan, V., Huang, S.-H.S., Hongfei Liu
Format: Conference Proceeding
Language:English
Subjects:
Binary search trees
Binary trees
Computer science
Dynamic programming
Equations
H infinity control
NASA
Open systems
Phase change random access memory
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).< >
DOI:10.1109/SPDP.1990.143590