| |
Table des matières de ce fascicule | Article précédent
Mahr, Bernd
Algebraic complexity of path problems. RAIRO, Informatique théorique, 16 no. 3 (1982), p. 263-292
Texte intégral djvu | pdf | Analyses MR 686917 | Zbl 0504.68023
URL stable: http://www.numdam.org/item?id=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
|
