کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875975 | 689609 | 2016 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs
ترجمه فارسی عنوان
مسیرهای غیرمستقیم در بسیاری از مسیرهای متفرق در گرافهای محدود مانند پیکربندی محدود می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
گراف بسیار شبه افراطی، مسیر متقابل، پوشش مسیر پارتیشن مسیر، تحمل خطا، شبکه متصل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
For two disjoint vertex-sets, S={s1,â¦,sk} and T={t1,â¦,tk} of a graph, an unpaired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {P1,â¦,Pk} that altogether cover every vertex of the graph, in which Pi is a path from si to some tj for 1â¤i,jâ¤k. A family of hypercube-like interconnection networks, called restricted hypercube-like graphs, includes most nonbipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Möbius cubes, recursive circulant G(2m,4) of odd m, etc. In this paper, we show that every m-dimensional restricted hypercube-like graph, mâ¥5, with at most f faulty vertices and/or edges being removed has an unpaired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each subject to kâ¥2 and f+kâ¤mâ1. The bound mâ1 on f+k is the maximum possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 617, 29 February 2016, Pages 45-64
Journal: Theoretical Computer Science - Volume 617, 29 February 2016, Pages 45-64
نویسندگان
Jung-Heum Park,