A systolic array algorithm for the algebraic path problem (shortest paths; Matrix inversion)

• Aho, A. V., Hopcroft, J. E., Ullmann, J. D.: The Design and Analysis of Computer Algorithms. Reading (Mass.)-London-Amsterdam: Addison-Wesley Publishing Co. 1975.

  Google Scholar 

• Backhouse, R. C., Carré, B. A.: Regular algebra applied to path-finding problems. J. Inst. Math. Appl.15, 161–186 (1975).

  Google Scholar 

• Brucker, P.: Theorie of Matrix Algorithms. Mathematical Systems in Economics 13. Meisenheim am Glan: Verlag Anton Hain 1974.

  Google Scholar 

• Carré, B. A.: An algebra for network routing problems. J. Inst. Math. Appl.7, 273–294 (1971).

  Google Scholar 

• Carré, B. A.: Graphs and Networks. Oxford: The Clarendon Press, Oxford University Press, 1979.

  Google Scholar 

• Floyd, R. N.: Algorithm 97 — shortest path. Comm. ACM5, 345 (1962).

  Article  Google Scholar 

• Gondran, M., Minoux, M.: Graphes et Algorithmes, Paris: Editions Eyrolles 1979.

  Google Scholar 

• Guibas, L. J., Kung, H. T., Thompson, C. D.: Direct VLSI Implementation of Combinatorial Algorithms. Proc. CalTech Conference on Very Large Scale Integration: Architecture, Design, Fabrication. California Institute of Technology, January 1979, Pasadena; Architecture session, pp. 509–525.

  Google Scholar 

• Kleene, S. C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.), Automata Studies pp. 3–40. Princeton (New Jersey): Princeton University Press 1956.

  Google Scholar 

• Kramer, M. R., van Leeuwen, J.: Systolic computation and VLSI. In: de Bakker, J. W., van Leeuven, J. (eds.), Foundations of Computer Science IV, part 1, pp 75–103. Math. Centre Tracts 158, Math. Centre, Amsterdam, 1983.

  Google Scholar 

• Kung, H. T.: The structure of parallel algorithms. In: Advances in Computers19, pp. 65–112. New York-London-Toronto-Sydney-San Francisco: Academic Press 1980.

  Google Scholar 

• Kung, H. T., Leiserson, C. E.: Systolic arrays (for VLSI). In: Duff, I. S., Stewart, G. W. (eds.), Sparse Matrix Proceedings 1978 (Sympos. Sparse Matrix Comput., Knoxville, Tenn. 1978), pp. 256–282. — SIAM, Philadelphia 1979. — (A slightly different version has appeared as section 8.3 of the book: Mead, C. A., Conway, L. A., Introduction to VLSI Systems. Reading (Mass.)-London-Amsterdam: Addison-Wesley Publishing Co. 1979.

  Google Scholar 

• Lehmann, D. J.: Algebraic structures for transitive closure Theoret. Comput. Sci.4, 59–76 (1977).

  Article  Google Scholar 

• Mahr, B.: Semirings and Transitive Closure. Technische Universität Berlin, Fachbereich 20, report 82-5 (1982).

• Mahr, B.: Iteration and summability in semirings. In: Burkard, R. E., Cuninghame-Green, R. A., Zimmermann, U. (eds.), Algebraic and Combinatorial Methods in Operations Research (Proceedings of the Workshop on Algebraic Structures in Operations Research, Bad Honnef, Federal Republic of Germany, April 13–17, 1982), Ann. Discrete Math.19, 229–256 (1984).

• Rote, G.: A Systolic Array for the Algebraic Path Problem (which Includes the Inverse of a Matrix and Shortest Distances in a Graph). Rechenzentrum Graz, Bericht RZG-101 (1984).

• Roy, B.: Transitivité et connexité. C. R. Acad. Sci. Paris Ser. A-B249, 216–218 (1959).

  Google Scholar 

• Tarjan, R. E.: A unified approach to path problems. J. Assoc. Comput. Mach.28, 577–593 (1981).

  Google Scholar 

• Warshall, S.: A theorem on Boolean matrices. J. Assoc. Comput. Mach.9, 11–12 (1962).

  Google Scholar 

• Zimmermann, U.: Linear and combinatorial optimization in ordered algebraic structures. (Especially chapter 8: Algebraic path problems) Ann. Discrete Math.10, 1–380 (1981).

  Google Scholar 

Download references