Algebraic complexity of path problems
Mahr, Bernd
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 263-292 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{ITA_1982__16_3_263_0,
     author = {Mahr, Bernd},
     title = {Algebraic complexity of path problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {263-292},
     mrnumber = {686917},
     zbl = {0504.68023},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_3_263_0}
}

Mahr, Bernd. Algebraic complexity of path problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 263-292. http://gdmltest.u-ga.fr/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 413592 | Zbl 0326.68005

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

[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 384339 | Zbl 0292.90049

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

[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 530382 | Zbl 0317.94045

[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 404050 | Zbl 0326.68027

[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 335175

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

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

[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 660291 | Zbl 0358.68061

[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 0449.68027

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

[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 659089 | Zbl 0484.68035

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

[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 395322

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

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

[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 449017

[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 429076 | Zbl 0327.05120

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