بهبود کیفیت آزمون در نرم‌افزارهای حساس به ایمنی با استفاده از آزمون جهش

•   آرشیو : نسخه پاییز 1397
•   موضوع : مهندسی نرم افزار
• نویسنده/گان : احسان خراطی
•   کلید واژه : الگوریتم موازی، جستجوی اول عمق گراف، مسائل NP-کامل و مسائل P-کامل
•   Title : Investigate parallel algorithms to first search for graph depth
•   Abstract :
  The study of the existence of parallel algorithms for the DFS problem in graphs has led to the creation of several ideas in this field. Tarjan and Tarjan-Hopcroft provided the first algorithm for DFS, and others tried to provide parallel algorithms in this area. This paper first examines the inherent "sequence" of the DFS algorithm by REIF, then Smith's study of the NC algorithm for flat graphs, and finally the study of the RNC algorithm by Anderson & Aggarwal. Which parallel algorithms are presented separately for the first search of graph depth
•   مراجع :
  [1] Reif, J, H. (1985) Depth-first search is inherently sequential. Information Processing Letters,
  20:229-234.
  [2] Reif, J, H. (1984) On synchronous parallel computations with independent probabilistic choice.
  SIAM Journal on Computing, 13(1):46-56.
  [3] Smith, J, R. (1986) Parallel algorithms for depth-first searches I. planar graphs. SIAM Journal
  on Computing, 15(3):814-830, August 1986.
  [4] Aggarwal, A. (1988) Anderson, R. J., A random NC algorithm for depth first search.
  Combinatorica, 8(1):1-12.
  [5] Aggarwal, A. (1990) Anderson, R. J., Kao, M. Y., Parallel depth-first search in
  general directed graphs. SIAM Journal on Computing, 19(2):397-409.
  [6] Anderson, R, J. (1986) A parallel algorithm for depth-first search. Extended Abstract, Mathematical Science Research Institute.
  [7] Anderson, R, J. (1987) A parallel algorithm for the maximal path problem. Combinatorica, 7(4):315-
  326.
•  صفحات : 26-45
•   دانلود فایل ( 941 KB )