A MORE EFFICIENT ALGORITHM FOR THE MIN-PLUS MULTIPLICATION

The (min, +) product C of two nxn matrices A and B is defined as Cij = [formulae omitted]. This paper presents an algorithm to compute the (min, +) product of two nxn matrices. The algorithm follows the approach described by Fredman. but is faster than Fredman's own algorithm: Its time complexity is either [formulae omitted] or even [formulae omitted] n), ifone adheres to the uniform-cost RAM model faithfully. This result implies the existence of [formulae omitted] n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem. As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model. © 1990 Gordon and Breach, Science Publishers, Inc.