Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
复制标题
DOI：
10.1016/j.jda.2009.01.001
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Ei Ando;Toshio Nakata;M. Yamashita
中科院分区：
文献类型：
--
作者：
Ei Ando;Toshio Nakata;M. Yamashita
本文提出了一种线性时间算法来逼近给定有向无环图(DAG)的最长路径长度，其中每条边的长度都是一个正态分布的随机变量。设F(X)是DAG的最长路径长度的分布函数。我们的算法计算正态分布的均值和方差，其分布函数F˜(X)满足F˜(X)⩽F(X)，只要F(X)⩾a，给定常数a(1/2⩽a<；1)。换句话说，它计算尾概率1−F(X)的上界1˜F−(X)，假设x⩾F−1(A)。为了评估F˜(X)逼近F(X)的精度，我们首先使用逻辑电路的标准基准集ITC‘99进行了两个实验，因为该算法的典型应用是逻辑电路的延迟分析。我们还进行了最坏情况分析，以得到差F˜−1(A)−F−1(A)的上界。
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).