کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874163 | 1441026 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The optimal routing of augmented cubes
ترجمه فارسی عنوان
مسیریابی مطلوب مکعب های تکمیل شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A routing in a graph G is a set of paths connecting each ordered pair of vertices. Load of an edge e is the number of times it appears on these paths. The edge-forwarding index of G is the smallest of maximum loads over all routings. Augmented cube of dimension n, AQn, is the Cayley graph (Z2n,{e1,e2,â¦,en,J2,â¦,Jn}) where ei's are the vectors of the standard basis and Ji=âj=nâi+1nej. S.A. Choudum and V. Sunitha showed that the greedy algorithm provides a shortest path between each pair of vertices of AQn. Min Xu and Jun-Ming Xu claimed that this routing also proves that the edge-forwarding index of AQn is 2nâ1. Here we disprove this claim, by showing that in this specific routing some edges are repeated nearly 432nâ1 times (to be precise, â2n+13â for even values of n and â2n+13â for odd values of n). However, by providing other routings, we prove that 2nâ1 is indeed the edge-forwarding index of AQn.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 136, August 2018, Pages 59-63
Journal: Information Processing Letters - Volume 136, August 2018, Pages 59-63
نویسندگان
Meirun Chen, Reza Naserasr,