PARALLEL DYNAMIC-PROGRAMMING

被引：12

作者：

HUANG, SHS

LIU, HF

VISWANATHAN, V

机构：

[1] Department of Computer Science., University of Houston, Houston

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1994年 / 5卷 / 03期

关键词：

PARALLEL ALGORITHMS; DYNAMIC PROGRAMMING; PRAM; ALGORITHM ANALYSIS; PROCESSOR REDUCTION;

D O I：

10.1109/71.277784

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Recurrence formulations for various problems such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangultion of polygons, assume a similar form. In [2], [5], a CREW PRAM algorithm was given to solve such dynamic programming problems. The algorithm uses O(n6/log n) processors and runs in O(log2n) time. In this short note, a modified algorithm is presented that reduces the processor requirement to O(n6/log 5n) while maintaining the same time complexity of O(log2n).

引用

页码：326 / 328

页数：3