| 摘要: |
| 定义了两类有向网络——ORC-网络和IRC-网络,并且提出一个计算它们的根通信可靠性(网络的一个特定结点(根点)能与其余每个结点通信的概率)的多项式时间算法.对于ORC-网络和IRC-网络,该算法的时间复杂度分别是O(｜E｜)和O(｜V｜·｜E｜),这里,｜V｜,｜E｜分别表示网络所含结点和边的数量. |
| 关键词: 网络,可靠性,算法,算法复杂性. |
| DOI： |
| 分类号: |
| 基金项目: |
|
| A Polynomial Time Algorithm for Computing Reliability of Two Classes of Networks |
|
KONG Fan-jia,WANG Guang-xing,ZHANG Xiang-de
|
| Abstract: |
| In this paper, two classes of directed networks——ORC-networks and IRC-networks are defined, and a polynomial time algorithm is presented for computing their rooted communication reliability, i.e. the probability that a specified vertex, root vertex, can communicate with all other vertices. The complexity of the algorithm for ORC-networks and IRC-networks is O(｜E｜) and O(｜V｜·｜E｜) respectively, where ｜V｜ and ｜E｜ are the number of vertices and of edges of networks respectively. |
| Key words: Network, reliability, algorithm, algorithm complexity. |
