Efficient matrix chain ordering in polylog time

This paper gives an O(lg³ n)-time and n/lg n processor algorithm for solving the matrix chain ordering problem and for finding optimal triangulations of a convex polygon on the common CRCW PRAM model. This algorithm works by finding shortest paths in special digraphs modeling dynamic programming tables. Also, a key part of the algorithm is improved by computing row minima of a totally monotone matrix, this lets the algorithm run in O(lg² n) time with n processors on the EREW PRAM or even O(lg² n lg lg n) time with n/lg lg n processors on the CRCW PRAM