BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-734
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Fast algorithms for solving path problems
        TYPE:: Technical Report
      AUTHOR:: Tarjan, Robert Endre
        DATE:: April 1979
       PAGES:: 50
    ABSTRACT:: Let G = (V,E) be a directed graph with a distinguished source
               vertex s. The single-source path expression problem is to
               find, for each vertex v, a regular expression P(s,v) which
               represents the set of all paths in G from s to v. A solution
               to this problem can be used to solve shortest path problems,
               solve sparse systems of linear equations, and carry out
               global flow analysis. We describe a method to compute path
               expressions by dividing G into components, computing path
               expressions on the components by Gaussian elimination, and
               combining the solutions. This method requires O(m
               $\alpha$(m,n)) time on a reducible flow graph, where n is the
               number of vertices in G, m is the number of edges in G, and
               $\alpha$ is a functional inverse of Ackermann's function. The
               method makes use of an algorithm for evaluating functions
               defined on paths in trees. A simplified version of the
               algorithm, which runs in O(m log n) time on reducible flow
               graphs, is quite easy to implement and efficient in practice.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-734