A more efficient algorithm for the min-plus multiplication

Abstract

The (min, + ) product C of two n × n matrices A and B is defined as C _ij = min_1≦k≦n A _ik + B _kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n ³/√log₂ n) or even O(n ^2.5√log₂ n), if one adheres to the uniform-cost RAM model faithfully.

This result implies the existence of O(n ³/√log₂ 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.

Keywords:

• Algorithms
• data structures
• matrix multiplication
• all-pairs shortest paths

^∗Research supported by NSERC grant OGP9110.

^∗Research supported by NSERC grant OGP9110.

Notes

^∗Research supported by NSERC grant OGP9110.