کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331031 | 686440 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Paired 2-disjoint path covers of multidimensional torus networks with faulty edges
ترجمه فارسی عنوان
مسیر زوج دو طرفه پوشش شبکه های چند بعدی جزیی با لبه های معیوب را پوشش می دهد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پوشش مسیر متصل نشده، تحمل خطا، چند منظوره محصول دلتای گراف، شبکه متصل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A paired k-disjoint path cover (paired k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. Clearly, the paired k-DPC is stronger than Hamiltonian-connectivity. The n-dimensional torus T(k1,k2,â¦,kn) (including the k-ary n-cube Qnk) is one of the most popular interconnection networks. In this paper, we obtain the following results. (1) Assume even kiâ¥4 for i=1,2,â¦,n. Let T=T(k1,k2,â¦,kn) be a bipartite torus and F be a set of faulty edges with |F|â¤2nâ3. Given any four vertices s1,t1,s2 and t2, such that each partite set contains two vertices. Then the graph TâF has a paired 2-DPC consisting of s1ât1 path and s2ât2 path. And the upper bound 2nâ3 of edge faults tolerated is optimal. The result is a generalization of the result of Park et al. concerning the case of n=2[17]. (2) Assume kiâ¥3 for i=1,2,â¦,n, with at most one ki being even. Let T=T(k1,k2,â¦,kn) be a torus and F be a set of faulty edges with |F|â¤2nâ4. Then the graph TâF has a paired 2-DPC. And the upper bound 2nâ4 of edge faults tolerated is nearly optimal. The result is a generalization of the result of Park concerning the case of n=2[16]. Our brief proofs are based on a technique that is of interest and may find some applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 107-110
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 107-110
نویسندگان
Xie-Bin Chen,