Algebraic complexity of path problems
RAIRO. Informatique théorique, Tome 16 (1982) no. 3, pp. 263-292. 
@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/}
}
TY  - JOUR
AU  - Mahr, Bernd
TI  - Algebraic complexity of path problems
JO  - RAIRO. Informatique théorique
PY  - 1982
SP  - 263
EP  - 292
VL  - 16
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1982__16_3_263_0/
LA  - en
ID  - ITA_1982__16_3_263_0
ER  - 
%0 Journal Article
%A Mahr, Bernd
%T Algebraic complexity of path problems
%J RAIRO. Informatique théorique
%D 1982
%P 263-292
%V 16
%N 3
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1982__16_3_263_0/
%G en
%F 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] A. V. Aho, J. E. Hopcroft and J. D. Ullman, Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. | MR | Zbl

[Be 76] C. Berge, Graphs and Hypergraphs, North Holland, 1976. | MR | Zbl

[Bl 80] P. Bloniarz, 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] P. Brucker, Theory of Matrix Algorithms, Math. Systems in Economics, 13, Anton Hain, 1974. | MR | Zbl

[Ca 79] B. A. Carré, Graphs and Networks, Clarendon Press, Oxford, 1979. | MR | Zbl

[DP 80] N. Deo and C. Pang, Shortest Path Algorithms: Taxonomy and Annotation, Washington State University, CS-80-057, 1980.

[Ei 74] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974. | MR | Zbl

[FM 71] M. J. Fischer and A. R. Meyer, Boolean Matrix Multiplication and Transitive Closure, I.E.E.E. 12th Ann. Symp. on Switching and Automata Theory, 1971.

[Fr 76] M. L. Fredman, New Bounds on the Complexity of the Shortest Path Problem, S.I.A.M. J. Comp., Vol. 5, 1976. | MR | Zbl

[IN 72] M. Iri and M. Nakamori, 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

[Jo 73] D. B. Johnson, Algorithms for Shortest Paths, TR 73-169, Cornell University, 1973. | MR

[Jo 77] D. B. Johnson, Efficient Algorithms for Shortest Paths in Networks, J. A.C.M., Vol. 24, 1977. | MR | Zbl

[Ke 70] L. R. Kerr, The Effect of Algebraic Structures on the Computational Complexity of Matrix Multiplication, Ph.D. Thesis, Cornell, 1970.

[Le 77] D. J. Lehmann, Algebraic Structures for Transitive Closure, Theoretical Computer Science, Vol. 4, 1977. | MR | Zbl

[LM 80] C. Lautemann and B. Mahr, A Note on the Complexity of Path Problems, unpublished, 1980.

[Ma 79] B. Mahr, Algebraische Komplexität des Allgemeinen Wegeproblems in Graphen, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 79-14, 1979(Thesis). | Zbl

[Ma 80] B. Mahr, A Birds-Eye View to Path Problems, LNCS, Vol. 100, Springer, Ed. Noltemeier, 1981. | MR | Zbl

[Ma 82] B. Mahr, Semirings and Transitive Closure, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 82-5, 1982.

[MS 81] B. Mahr and D. Siefkes, Relating Uniform and Nonuniform Models of Computation, Informatik Fachberichte, Springer, Vol. 50, Braner, Ed., 1981. | MR | Zbl

[Me 77] K. Mehlhorn, Effiziente Algorithmen, Teubner, 1977. | MR | Zbl

[MU 68] J. D. Murchland, Shortest Distances by a Fixed Matrix Method, Report LBS-TNT-64, London, Graduate School of Business Studies, 1968 (see [Br 74]).

[Pa 74] M. S. Paterson, Complexity of Matrix Algorithms, handwritten copy, May 1974. | MR

[PR 75] V. R. Pratt, The Power of Negative Thinking in Multiplying, Boolean Matrices, S.I.A.M. J. Comp., Vol. 4, 1975. | MR | Zbl

[Ro 80] F. Romani, Shortest Path Problems is not Harder than Matrix Multiplication, Information Processing Letters, Vol. 11, No. 3, 1980. | MR | Zbl

[SP 73] P. M. Spira and A. Pan, On Finding and Updating Shortest Paths and Spanning Trees, 14th Ann. Symp. on Switching and Automata Theroy, 1973. | MR

[TA 75] R. E. Tarjan, Solving Path Problems on Directed Graphs, Comp. Sc. Dept. Univ. Stanford, 1975.

[Wa 76] R. A. Wagner, A Shortest Path Algorithm for Edge Sparse Graphs, J. A.C.M., Vol. 23, 1976. | MR | Zbl

[Zi 81] U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures, 1981 (to appear). | MR | Zbl