Cluster Fault Tolerant Routing in Star Graphs

概要

論文の詳細を見る
In this paper,we study the node fault tolerant routing properties of n-dimensional star graphs G_nbased on the cluster fault tolerant routing model which is a natural extension of the well studied node fault tolerant routing.For a graph G,a cluster C is a connected subgraph of G,and C is called fault cluster if all nodes in C are faulty.In cluster fault tolerant routing,the number of fault clusters and the size of the fault clusters that can be tolerated are studied.For node-to-node,node-to-set,set-to-set,and k-pairwise fault tolerant routing problems in n-dimensional star graphs G_n,we prove that G_n can tolerate n - 2,n - 1 - k,n - 1 - k,and n - 2k fault clusters of diameter at most 2,respectively.Our results show that stax graphs G_nhave very good node fault tolerant routing properties.Wealso give optimal time algorithms which find the required routing paths of length d(G_n)+ O(1)for any tolerable set of fault clusters in the above routing problems, where d(G_n)=[(3(n-1)), 2]is the diameter of G_n.
社団法人電子情報通信学会の論文
1994-10-21