Fast Algorithms for Solving Path Problems
Robert Endre Tarjan · Journal of the ACM · 1981
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.A method is described for computing path expressions by dwidmg G mto components, computing path expressions on the components by Gaussian elimination, and combining the solutions This method requires O(ma(m, n)) time on a reducible flow graph, where n Is the number of vertices m G, m is the number of edges in G, and a is a functional inverse of Ackermann's function The method makes use of an algonthm for evaluating functions defined on paths in trees.A smapllfied version of the algorithm, which runs in O(m log n) time on reducible flow graphs, is quite easy to implement and efficient m practice KEY WORDS AND PHRASES: Ackermann's function, code optimizaUon, compdmg, dominators, Gaussian ehmmaUon, global flow analysis, graph algorithm, linear algebra, path compression, path expression, path problem, path sequence, reducible flow graph, regular expressmn, shortest path, sparse matrix CR CATEGORIES 4 12, 4.34, 5 14, 5.22, 5.25, 5 32 paths from s to v in G.By reinterpreting the U,., and * operations used to construct regular expressions, we can use a solution to the single-source path expression problem to solve other kinds of path problems, including those mentioned above [30].We thus obtain a general-purpose algorithm for solving any path problem on a given graph.This paper describes a decomposition method for computing path expressions.The method divides the graph G into components based upon the dominator tree of G, computes a path expression for each component by Gaussian elimination, and combines the solutions using an algorithm for evaluating functions defined on trees [9, 29].The algorithm requires O(mct(m, n)) time plus time to compute path expressions within the components, where n is the number of vertices in G, m is the Permission to copy without fee all or part of this matenal is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the pubhcatlon and its date appear, and notice is given that copying is by permlssmn of the Association for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission