The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                   Uri Zwick
                              Tel-Aviv University


                                 will speak on


           All pairs shortest paths using fast matrix multiplication

Abstract:
Several recent algorithms for solving the all pairs shortest paths (APSP)
problem in graphs will be discussed. All these algorithms use fast algorithms
for algebraic matrix multiplication. Among the algorithms is an $O(n^{2.575})$
time algorithm for solving the APSP problem in unweighted directed graphs, and
an $O(n^\omega)$ time algorithm for solving the problem in unweighted
undirected graphs, where $\omega<2.376$ is the exponent of algebraic matrix
multiplication.




                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                          on Monday, November 29, 1999
                                    at 14:30