A more efficient algorithm for the min-plus multiplication

References

• Bloniarz , P. 1980 . 12th Annual ACM Symposium on Theory of Computing . A shortest path algorithm with expected time O(n 2log n log∗ n) . 1980 . pp. 378 – 384 .
   Google Scholar
• Carson , J. S. and Law , A. M. 1977 . A note on Spira's algorithm for the all-pairs shortest-path problem . SIAM Journal on Computing , 6 ( 4 ) : 696 – 699 .
   Web of Science ®Google Scholar
• Fischer , M. J. and Meyer , A. R. 1971 . IEEE 12th Annual Symposium on Switching and Automata Theory . Boolean matrix multiplication and transitive closure . 1971 . pp. 129 – 131 .
   Google Scholar
• Fredman , M. L. 1976 . New bounds on the complexity of the shortest path problem . SIAM Journal on Computing , 5 ( 1 ) : 83 – 89 .
   Google Scholar
• Kerr L. R. The effect of algebraic structure on the computational complexity of matrix multiplications Cornell University 1970 Ph.D. thesis
   Google Scholar
• Mehlhorn , K. 1984 . Data Structures and Algorithms 2: Graph Algorithms and NP-completeness , 155 – 158 . Springer-Verlag .
   Google Scholar
• Munro , I. 1971 . Efficient determination of the transitive closure of a directed graph . Information Processing Letters , 1 : 56 – 58 .
   Google Scholar
• Romani , F. 1980 . Shortest-path problem is not harder than matrix multiplication . Information Processing Letters , 11 : 134 – 136 .
   Web of Science ®Google Scholar
• Spira , P. M. 1973 . A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n 2 log2 n) . SIAM Journal on Computing , 2 : 28 – 32 .
   Google Scholar