We study node-to-set and set-to-set fault tolerant routing problems is n-dimensional hypercubes H_n. node-to-set routing problem is that given a node s and a set of nodes T={t_1,..., t_k}, finds k node-disjoint paths s→t_i, 1≤i≤k. Set-to-set routing problem is that Given two sets of nodes S={s_1,...,s_k}and T={t_1,...,t_k}, finds k node-disjoint paths, each Path connects a node of S and a node of T. From Menger's theorem, it is known that these two Problems in H_n can tolerate at most n-k arbitrary faulty nodes. In this paper, we prove that Both routing problems can tolerate n-k arbitrary subgraphs(called cluster)of diam- Eter 1.
展开▼
