Shortest-path problem is not harder than matrix multiplication. (English) Zbl 0454.68069


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI


[1] Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA
[2] Fisher, M. J.; Meyer, A. R., Boolean matrix multiplication and transitive closure, Proc. \(12^{th}\) Annual Symposium on Switching and Automata Theory, 129-131 (1971)
[3] Pan, V. Ya., Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplication, Proc. \(20^{th}\) Annual Symposium on Foundation of Computer Science, 28-38 (1979)
[5] Schönhage, A., Partial and total matrix multiplication, (Internal Report (1980), University of Tübingen) · Zbl 0462.68018
[6] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[7] Yuval, G., An algorithm for finding all the shortest paths using \(N^{2.81}\) infinite-precision multiplications, Information Processing Lett., 4, 155-156 (1976) · Zbl 0333.68034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.