摘要： k元n树是一种用于大规模并行处理的高性能互联网络的拓扑结构。该文提出计算k元n树的2-终点可靠性的递归算法，其计算复杂度为O(n)。结合市场上网络元器件可靠性的实际情况，对k元n树的2-终点可靠性进行了分析。当n趋于无穷大时，计算出k元n树的2-终点可靠性的下限。

关键词: k元n树, 2-终点可靠性, 计算复杂度, 下限

Abstract: k-ary n-tree is a kind of topology of high performance interconnection networks for parallel architectures. A recursive algorithm is presented to calculate two-terminal reliability of k-ary n-tree. Its computational complexity is O(n). Taking the reliability of commercial network components into consideration, this paper analyzes two-terminal reliability of k-ary n-trees. When n tends to be infinite, the lower bound of two-terminal reliability of k-ary n-tree is given.

Key words: k-ary n-tree, two-terminal reliability, computational complexity, lower bound

中图分类号: 

• TP393