کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
394623 | 665817 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Long paths in hypercubes with a quadratic number of faults
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A path between distinct vertices u and v of the n -dimensional hypercube QnQn avoiding a given set of f faulty vertices is called long if its length is at least 2n-2f-22n-2f-2. We present a function ϕ(n)=Θ(n2)ϕ(n)=Θ(n2) such that if f⩽ϕ(n)f⩽ϕ(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of QnQn. Moreover, the bound provided by ϕ(n)ϕ(n) is asymptotically optimal. Furthermore, we show that assuming f⩽ϕ(n)f⩽ϕ(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 179, Issue 21, 18 October 2009, Pages 3763–3771
Journal: Information Sciences - Volume 179, Issue 21, 18 October 2009, Pages 3763–3771
نویسندگان
Tomáš Dvořák, Václav Koubek,