A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem
Mounir Kechid, Jean‐Frédéric Myoupo · 2008
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(n2) time steps and O(n2) space. Our CGM (coarse grain multicomputer) algorithm uses p processors, each with O(n2/p) local memory. It requires O(p) communication rounds and O(n2/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.