The Algebraic Path Problem Revisited

1. A. Benaini, P. Quinton, Y. Robert, Y. Saouter, and B. Tourancheau. Synthesis of a new systolic architecture for the algebraic path problem. Science of Computer Programming. 15:135–158, 1990.

   Article  MathSciNet  Google Scholar 

2. A. Benaini and Y. Robert. Space-time minimal systolic arrays for gaussian elimination and the algebraic path problem. In ASAP 90: International Conference on Application Specific Array Processors, pages 746–757, Princeton, NJ, September 1990. IEEE Press.

   Google Scholar 

3. P.Y. Chang and J.C. Tsay. A family of efficient regular arrays for the algebraic path problem. IEEE Transactions on Computers, 43(7):769–777, July 1994.

   Article  Google Scholar 

4. P. Clauss, C. Mongenet, and G-R. Perrin. Synthesis of size-optimal toroidal arrays for the algebraic path problem: A new contribution. Parallel Computing, 18:185–194, 1992.

   Article  Google Scholar 

5. L. Guibas, H.T. Kung, and Clark D. Thompson. Direct VLSI implementation of combinatorial algorithms. In Proc. Conference on Very Large Scale Integration: Architecture, Design and Fabrication, pages 509–525, January 1979.

   Google Scholar 

6. S.Y. Kung and S.C. Lo. A spiral systolic algorithm/architecture for transitive closure problems. In ICCD 85: International Conference on Circuit Design, pages 622–626, Rye Town, NY, 1985. IEEE.

   Google Scholar 

7. S.Y. Kung, S.C. Lo, and P.S. Lewis. An op timal systolic design for the transitive closure and the shortest path problems. IEEE Transactions on Computers, C-36(5):603–614, May 1987.

   Article  Google Scholar 

8. J.F. Myoupo and C. Fabret. A modular systolic linearization of the warshall-floyd algorithm. IEEE Transactions on Parallel and Distributed Systems, 7(5):449–455, may 1996.

   Article  Google Scholar 

9. J.G. Nash and S. Hansen. Modified faddeew algorithm for matrix multiplication. In Proc., SPIE Workshop on Real-Time Signal Processing, pages 39–46. SPIE, 1984.

   Google Scholar 

10. V.K. Prasanna Kumar and Y-C Tsai. Designing linear systolic arrays. Journal of Parrallel and Distributed Computing, (7):441–463, may 1989.

    Google Scholar 

11. S.V. Rajopadhye. An improved systolic algorithm for the algebraic path problem. INTEGRATION: The VLSI Journal, 14(3):279–296, Feb 1993.

    Article  Google Scholar 

12. T. Risset and Y. Robert. Synthesis of processors arrays for the algebraic path problem: Unifying old results and deriving new architectures. Parallel Processing Letters, 1:19–28, 1991.

    Article  Google Scholar 

13. Y. Robert and M. Tchuent. FrRsolution systolique de systmes linaires denses. RAIRO Modlisation et Analyse Numrique, Technique et Sciences Informatiques, 19(2):315–326, 1985.

    Google Scholar 

14. Y. Robert and D. Trystam. Systolic solution of the algebraic path problem. In W. Moore, A. McCabe, and R. Urquhart, editors, Systolic Arrays, 1, pages 171–180, Oxford, UK, 1987. Adam Hilger.

    Google Scholar 

15. Günter Rote. A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion). Computing, 34(3):191–219, 1985.

    Article  MathSciNet  Google Scholar 

16. Chris J. Schieman and Peter R. Cappello. A processor-time minimal systolic array for transitive closure. In International Conference on Application Specific Array Processors, pages 19–30, Princeton, NJ, September 1990. IEEE Computer Society, IEEE Computer Society Press.

    Google Scholar 

17. T. Takaoka and K. Umehara. An efficient VLSI circuit for the all pairs shortest path problem. Journal of Parallel and Distributed Computing, 16:265–270, 1992.

    Article  MathSciNet  Google Scholar 

18. C. Tayou Djamegni, P. Quinton, S. Rajopadhye, and T. Risset. Derivation of systolic algorithms for the algebraic path problem by recurrence transformations. Parallel Computing, To appear, 1999.

    Google Scholar 

Download references