کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431765 688624 2006 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Average case analysis of DJ graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Average case analysis of DJ graphs
چکیده انگلیسی

Sreedhar et al. [V.C. Sreedhar, G.R. Gao, Y.-F. Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Trans. Program. Lang. Syst. 20 (2) (1998) 388–435; V.C. Sreedhar, Efficient program analysis using DJ graphs, PhD thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, 1995] have presented an elimination-based algorithm to solve data flow problems. A thorough analysis of the algorithm shows that the worst-case performance is at least quadratic in the number of nodes of the underlying graph. In contrast, Sreedhar reports a linear time behavior based on some practical applications.In this paper we prove that for goto-free programs, the average case behavior is indeed linear. As a byproduct our result also applies to the average size of the so-called dominance frontier.A thorough average case analysis based on a graph grammar is performed by studying properties of the j-edges in DJ graphs. It appears that this is the first time that a graph grammar is used in order to analyze an algorithm. The average linear time of the algorithm is obtained by classic techniques in the analysis of algorithms and data structures such as singularity analysis of generating functions and transfer lemmas.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 4, Issue 4, December 2006, Pages 649–675
نویسندگان
,