کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333165 | 688607 | 2009 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 420-438
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 420-438
نویسندگان
Ei Ando, Toshio Nakata, Masafumi Yamashita,