The concept of strong fault-tolerance was introduced to characterize the property of parallel routing. A network G of degree d is said to be strongly fault-tolerant if with at most d-2 faulty nodes, any two nodes u and v in G are connected by min{deg/sub f/(u), deg/sub f/(v)} node-disjoint paths, where deg/sub f/ (u) and deg/sub f/ (v) are the numbers of non-faulty neighbors of the nodes u and v in G, respectively. We show that the hypercube networks are strongly fault-tolerant and develop an algorithm that constructs the maximum number of node-disjoint paths in a hypercube network with faults. Our algorithm is optimal in terms of time and length of node-disjoint paths.
展开▼
机译：引入强容错的概念来表征并行路由的特性。如果具有最多d-2个故障节点，则G中的任意两个节点u和v通过min {deg / sub f /（u），deg / sub f连接，则表示度为d的网络G是高度容错的。 /（v）}节点不相交的路径，其中deg / sub f /（u）和deg / sub f /（v）分别是G中节点u和v的无故障邻居的数量。我们证明了超立方体网络是高度容错的，并开发了一种算法，该算法可在有故障的超立方体网络中构造最大数量的节点不相交路径。我们的算法在时间和节点不相交路径的长度方面都是最佳的。
展开▼
