文摘
This paper considers the problem of many-to-many disjoint paths in the hypercube QnQn with ff faulty vertices and obtains the following result. For any integer kk with 1≤k≤n−11≤k≤n−1 and any two sets SS and TT of kk fault-free vertices in different partite sets of Qn(n≥2), if f≤2n−2k−2f≤2n−2k−2 and each fault-free vertex has at least two fault-free neighbors, then there exist kk fully disjoint fault-free paths linking SS and TT which contain at least 2n−2f2n−2f vertices. A linear algorithm for finding such disjoint paths is also given. This result improves some known results in a sense.