Approximating the longest path length of a stochastic DAG by a normal distribution in linear time

This paper presents a linear time algorithm for approximating, in the sense below, the longest path length of a given directed acyclic graph (DAG), where each edge length is given as a normally distributed random variable. Let F(x) be the distribution function of the longest path length of the DAG. Our algorithm computes the mean and the variance of a normal distribution whose distribution function F˜(x) satisfies F˜(x)⩽F(x) as long as F(x)⩾a, given a constant a (1/2⩽a<1). In other words, it computes an upper bound 1−F˜(x) on the tail probability 1−F(x), provided x⩾F−1(a). To evaluate the accuracy of the approximation of F(x) by F˜(x), we first conduct two experiments using a standard benchmark set ITC'99 of logical circuits, since a typical application of the algorithm is the delay analysis of logical circuits. We also perform a worst case analysis to derive an upper bound on the difference F˜−1(a)−F−1(a).