Title :
Parallel dynamic programming
Author :
Viswanathan, Venkatraman ; Huang, Shou-Hsuan Stephen ; Liu, Hongfei
Author_Institution :
Dept. of Comput. Sci., Houston Univ., TX, USA
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(n6/log n ) processors and runs in O(log2 n)time. A modified algorithm is presented which reduces the processor requirement to O(n6/log5 n) while maintaining the same time complexity of O (log2 n)
Keywords :
computational complexity; dynamic programming; matrix algebra; parallel algorithms; search problems; trees (mathematics); CREW PRAM algorithm; binary search tree; dynamic programming; matrix multiplication; parallel algorithms; polygons; recurrence formulations; time complexity; triangulation; Binary search trees; Binary trees; Computer science; Dynamic programming; Equations; H infinity control; NASA; Open systems; Phase change random access memory;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143590
