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) 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 F ( x ) ? a , given a constant a  (1/2?a<1 1 / 2 ? a < 1 ). In other words, it computes an upper bound 1 ? F  ( x ) on the tail probability 1?F(x) 1 ? F ( x ) , provided x?F?1(a) x ? F ? 1 ( a ) . To evaluate the accuracy of the approximation of F(x) 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 ) .
approximation normal distribution directed acyclic graph longest path problem stochastic edge weight