Algebraic complexity of path problems

 Access to full text

 Full (PDF)

1. [AHU 74] A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. Zbl0326.68005MR413592
2. [Be 76] C. BERGE, Graphs and Hypergraphs, North Holland, 1976. Zbl0311.05101MR384579
3. [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. 
4. [Br 74] P. BRUCKER, Theory of Matrix Algorithms, Math. Systems in Economics, 13, Anton Hain, 1974. Zbl0292.90049MR384339
5. [Ca 79] B. A. CARRÉ, Graphs and Networks, Clarendon Press, Oxford, 1979. Zbl0455.05001MR556411
6. [DP 80] N. DEO and C. PANG, Shortest Path Algorithms: Taxonomy and Annotation, Washington State University, CS-80-057, 1980. 
7. [Ei 74] S. EILENBERG, Automata, Languages and Machines, Vol. A, Academic Press, 1974. Zbl0317.94045MR530382
8. [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. 
9. [Fr 76] M. L. FREDMAN, New Bounds on the Complexity of the Shortest Path Problem, S.I.A.M. J. Comp., Vol. 5, 1976. Zbl0326.68027MR404050
10. [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. Zbl0245.05106MR335175
11. [Jo 73] D. B. JOHNSON, Algorithms for Shortest Paths, TR 73-169, Cornell University, 1973. MR2623424
12. [Jo 77] D. B. JOHNSON, Efficient Algorithms for Shortest Paths in Networks, J. A.C.M., Vol. 24, 1977. Zbl0343.68028MR449710
13. [Ke 70] L. R. KERR, The Effect of Algebraic Structures on the Computational Complexity of Matrix Multiplication, Ph.D. Thesis, Cornell, 1970. 
14. [Le 77] D. J. LEHMANN, Algebraic Structures for Transitive Closure, Theoretical Computer Science, Vol. 4, 1977. Zbl0358.68061MR660291
15. [LM 80] C. LAUTEMANN and B. MAHR, A Note on the Complexity of Path Problems, unpublished, 1980. 
16. [Ma 79] B. MAHR, Algebraische Komplexität des Allgemeinen Wegeproblems in Graphen, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 79-14, 1979(Thesis). Zbl0449.68027
17. [Ma 80] B. MAHR, A Birds-Eye View to Path Problems, LNCS, Vol. 100, Springer, Ed. Noltemeier, 1981. Zbl0454.68070MR621510
18. [Ma 82] B. MAHR, Semirings and Transitive Closure, Techn. Univ. Berlin, Fachbereich Informatik, Vol. 82-5, 1982. 
19. [MS 81] B. MAHR and D. SIEFKES, Relating Uniform and Nonuniform Models of Computation, Informatik Fachberichte, Springer, Vol. 50, Braner, Ed., 1981. Zbl0484.68035MR659089
20. [Me 77] K. MEHLHORN, Effiziente Algorithmen, Teubner, 1977. Zbl0357.68041MR495158
21. [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]). 
22. [Pa 74] M. S. PATERSON, Complexity of Matrix Algorithms, handwritten copy, May 1974. MR395322
23. [PR 75] V. R. PRATT, The Power of Negative Thinking in Multiplying, Boolean Matrices, S.I.A.M. J. Comp., Vol. 4, 1975. Zbl0318.94040MR403831
24. [Ro 80] F. ROMANI, Shortest Path Problems is not Harder than Matrix Multiplication, Information Processing Letters, Vol. 11, No. 3, 1980. Zbl0454.68069MR593406
25. [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. MR449017
26. [TA 75] R. E. TARJAN, Solving Path Problems on Directed Graphs, Comp. Sc. Dept. Univ. Stanford, 1975. 
27. [Wa 76] R. A. WAGNER, A Shortest Path Algorithm for Edge Sparse Graphs, J. A.C.M., Vol. 23, 1976. Zbl0327.05120MR429076
28. [Zi 81] U. ZIMMERMANN, Linear and Combinatorial Optimization in Ordered Algebraic Structures, 1981 (to appear). Zbl0466.90045MR609751