@article{ITA_1982__16_3_263_0, author = {Mahr, Bernd}, title = {Algebraic complexity of path problems}, journal = {RAIRO. Informatique th\'eorique}, pages = {263--292}, publisher = {EDP-Sciences}, volume = {16}, number = {3}, year = {1982}, mrnumber = {686917}, zbl = {0504.68023}, language = {en}, url = {http://www.numdam.org/item/ITA_1982__16_3_263_0/} }
Mahr, Bernd. Algebraic complexity of path problems. RAIRO. Informatique théorique, Tome 16 (1982) no. 3, pp. 263-292. http://www.numdam.org/item/ITA_1982__16_3_263_0/
[AHU 74] Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. | MR | Zbl
, and ,[Be 76] Graphs and Hypergraphs, North Holland, 1976. | MR | Zbl
,[Bl 80] A Shortest Path Algorithm with Expected Time O (n2 log n log * n), Proc. of the 12th A.C.M. Symp. on Theory of Computing, Los Angeles, 1980.
,[Br 74] Theory of Matrix Algorithms, Math. Systems in Economics, 13, Anton Hain, 1974. | MR | Zbl
,[Ca 79] Graphs and Networks, Clarendon Press, Oxford, 1979. | MR | Zbl
,[DP 80] Shortest Path Algorithms: Taxonomy and Annotation, Washington State University, CS-80-057, 1980.
and ,[Ei 74] Automata, Languages and Machines, Vol. A, Academic Press, 1974. | MR | Zbl
,[FM 71] Boolean Matrix Multiplication and Transitive Closure, I.E.E.E. 12th Ann. Symp. on Switching and Automata Theory, 1971.
and ,[Fr 76] New Bounds on the Complexity of the Shortest Path Problem, S.I.A.M. J. Comp., Vol. 5, 1976. | MR | Zbl
,[IN 72] Path Sets, Operator Semigroups and Shortest Path Algorithms on a Network, R.A.A.G, Research Notes, Third Series, No. 185, Univ. Tokyo, 1972. | MR
and ,[Jo 73] Algorithms for Shortest Paths, TR 73-169, Cornell University, 1973. | MR
,[Jo 77] Efficient Algorithms for Shortest Paths in Networks, J. A.C.M., Vol. 24, 1977. | MR | Zbl
,[Ke 70] The Effect of Algebraic Structures on the Computational Complexity of Matrix Multiplication, Ph.D. Thesis, Cornell, 1970.
,[Le 77] Algebraic Structures for Transitive Closure, Theoretical Computer Science, Vol. 4, 1977. | MR | Zbl
,[LM 80] A Note on the Complexity of Path Problems, unpublished, 1980.
and ,[Ma 79] Algebraische Komplexität des Allgemeinen Wegeproblems in Graphen, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 79-14, 1979(Thesis). | Zbl
,[Ma 80] A Birds-Eye View to Path Problems, LNCS, Vol. 100, Springer, Ed. Noltemeier, 1981. | MR | Zbl
,[Ma 82] Semirings and Transitive Closure, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 82-5, 1982.
,[MS 81] Relating Uniform and Nonuniform Models of Computation, Informatik Fachberichte, Springer, Vol. 50, Braner, Ed., 1981. | MR | Zbl
and ,[Me 77] Effiziente Algorithmen, Teubner, 1977. | MR | Zbl
,[MU 68] Shortest Distances by a Fixed Matrix Method, Report LBS-TNT-64, London, Graduate School of Business Studies, 1968 (see [Br 74]).
,[Pa 74] Complexity of Matrix Algorithms, handwritten copy, May 1974. | MR
,[PR 75] The Power of Negative Thinking in Multiplying, Boolean Matrices, S.I.A.M. J. Comp., Vol. 4, 1975. | MR | Zbl
,[Ro 80] Shortest Path Problems is not Harder than Matrix Multiplication, Information Processing Letters, Vol. 11, No. 3, 1980. | MR | Zbl
,[SP 73] On Finding and Updating Shortest Paths and Spanning Trees, 14th Ann. Symp. on Switching and Automata Theroy, 1973. | MR
and ,[TA 75] Solving Path Problems on Directed Graphs, Comp. Sc. Dept. Univ. Stanford, 1975.
,[Wa 76] A Shortest Path Algorithm for Edge Sparse Graphs, J. A.C.M., Vol. 23, 1976. | MR | Zbl
,[Zi 81] Linear and Combinatorial Optimization in Ordered Algebraic Structures, 1981 (to appear). | MR | Zbl
,