2002 · 12 citations · 2 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisComputational ComplexityDynamic ProgrammingParallel Algorithm DesignParallel Computational GeometryParallel Computing SystemsBinary SearchBinary Search TreesComplexity Of Dynamic ProgrammingMatrix MultiplicationOptimal Polygon TriangulationParallel Dynamic ProgrammingParallel Time ComplexityPram Algorithms
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).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
2
Donald E. Knuth · Acta Informatica · 1971 · 448 citations