PARALLEL DYNAMIC-PROGRAMMING

Authors
HUANG SHS LIU HF VISWANATHAN V
Citation
Shs. Huang et al., PARALLEL DYNAMIC-PROGRAMMING, IEEE transactions on parallel and distributed systems, 5(3), 1994, pp. 326-328
Citations number
5
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
5
Issue
3
Year of publication
1994
Pages
326 - 328
Database
ISI
SICI code
1045-9219(1994)5:3<326:PD>2.0.ZU;2-M
Abstract
Recurrence formulations for various problems such as finding an optima l order of matrix multiplication, finding an optimal binary search tre e, and optimal triangultion of polygons, assume a similar form. In [2] , [5], a CREW PRAM algorithm was given to solve such dynamic programmi ng problems. The algorithm uses O(n6/log n) processors and runs in O(l og2n) time. In this short note, a modified algorithm is presented that reduces the processor requirement to O(n6/log 5n) while maintaining t he same time complexity of O(log2n).