کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333882 | 689653 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Paired 2-disjoint path covers of faulty k-ary n-cubes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Paired 2-disjoint path covers of faulty k-ary n-cubes Paired 2-disjoint path covers of faulty k-ary n-cubes](/preview/png/10333882.png)
چکیده انگلیسی
A paired k-disjoint path cover of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. The k-ary n-cube Qnk is one of the most popular interconnection networks. In this paper, we consider the problem of paired 2-disjoint path covers of the k-ary n-cube Qnk (odd kâ¥5) with faulty elements (vertices and/or edges) and obtain the following result. Let F be a set of faulty elements in Qnk (odd kâ¥5) with |F|â¤2nâ4, and {a,b} and {c,d} be its any two pairs of non-faulty vertices. Then the graph QnkâF contains vertex-disjoint aâb path and câd path that cover its all non-faulty vertices, and the upper bound 2nâ4 of faults tolerated is nearly optimal. We also show that Cartesian product QnkÃP with at most 2nâ2 faulty elements is Hamiltonian connected, where P is a path, nâ¥2 and odd kâ¥5.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 494-499
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 494-499
نویسندگان
Xie-Bin Chen,