A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem

This paper presents a CGM parallel algorithm for the cost of the optimal binary search tree problem (OBST problem). The best sequential algorithm for this problem, due to Knuth, requires O(n²) time steps and O(n²) space. Our CGM (coarse grain multicomputer) algorithm uses p processors, each with O(n²/p) local memory. It requires O(p) communication rounds and O(n²/p) local computations per processor. To the best of our knowledge, it is the first CGM parallel algorithm, based on the Knuth sequential version of the OBST problem.