Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333165 | Journal of Discrete Algorithms | 2009 | 19 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ei Ando, Toshio Nakata, Masafumi Yamashita,