تخطي إلى التنقل الرئيسي تخطي إلى البحث تخطي إلى المحتوى الرئيسي

Parallel algorithms for the network all-terminal reliability problem

نتاج البحث: Article › مراجعة النظراء

ملخص

We consider an unreliable computer communication network, where the links are subject to random failures with known probabilities. In this case, the failure of one or more links may cause some of the sites to be disconnected from the rest of the network. The all-terminal reliability problem is computing the probability that the sites can communicate with each other, i.e. there exists an operational path between every pair of sites in the network. In this paper, we exploit the parallelism of the all-terminal problem and present two parallel algorithms for computing all-terminal reliability. The first computes the all-terminal reliability for arbitrary networks using the factoring theorem and graph reductions, and requires time bounded by a polynomial in the number of spanning trees in the network. The second parallel algorithm computes the all-terminal reliability for series-parallel networks. This algorithm requires O(log2n+m) time with O(n+m) processors, where n is the number of sites, and m is the number of links in the network.

اللغة الأصليةEnglish
الصفحات (من إلى)151-162
عدد الصفحات12
دوريةKuwait Journal of Science and Engineering
مستوى الصوت23
رقم الإصدارSUPPL. 2
حالة النشرPublished - 1996

بصمة

أدرس بدقة موضوعات البحث “Parallel algorithms for the network all-terminal reliability problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا