一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法，可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性，可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示，并且当且仅当两个簇相邻时，两个结点间的互连由边表示。这个概率图的链路完全可靠，并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。

A Linear-time Algorithm for Computing Ad hoc Network K-terminal Reliability of MANET

This paper studies linear-time algorithm for computing K-terminal reliability of MANET, may quickly compute K-terminal reliability of MANET. In order to computing K-terminal reliability of MANET hier-achical structure, MANET hierachical structure can be modeled using an undirected probabilistic graph, in which each cluster header is represented by a vertex with known probability of failure, and edge exists between the vertices iff the related clusters are adjacent. Consider a probabilistic graph in which the edges are perfectly reliable, but vertices can fail with some known probabilities. The K-terminal reliability of this graphs is the probability that a given set of vertices K is connected. This paper presents a linear-time algorithm for computing K-terminal reliability on proper interval graphs. This algorithm can be used for computing K-terminal reliability of MANET. This algorithm can be implemented in O（｜V｜ ＋ ｜E｜ ） time.