کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949738 1440204 2017 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The wide-diameter of Zn,k
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The wide-diameter of Zn,k
چکیده انگلیسی
The l-wide-diameter of a graph G is the minimum integer d for which there exist at least l internally disjoint paths of length at most d between any two distinct vertices in G. This parameter measures the fault tolerance and transmission delay in communication networks modelled by graphs. Hypercube-like graphs are widely used as graph models for interconnection networks. In this paper, we study the wide-diameters of a special type of hypercube-like graphs: the Z-cubes Zn,k. It is known that Zn,k have diameter at most ⌈nk+1⌉+2k in Zhu (2015). We show that the k-wide-diameter of Zn,k is at most ⌈nk+1⌉+2k+k+4. In particular, if k=⌈log2n−2log2log2n⌉, then the k-wide-diameter of Zn,k is (1+o(1))nlog2n, which is asymptotically optimal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 193-201
نویسندگان
, ,