Many-to-many disjoint paths in hypercubes with faulty vertices

详细信息    查看全文

• 作者：Xiang-Jun Li^a ; ^{franklxj@mail.ustc.edu.cn} ; Bin Liu^b ; ^{binliu1009@gmail.com} ; Meijie Ma^c ; ^{mameij@zjnu.cn} ; Jun-Ming Xu^d ; ^{xujm@ustc.edu.cn}
• 关键词：Hypercube ; Disjoint paths ; Fault-tolerance ; Parallel computing
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：229-242
• 全文大小：597 K
• 卷排序：217

文摘

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.