کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
394453 665805 2010 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improving bounds on link failure tolerance of the star graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Improving bounds on link failure tolerance of the star graph
چکیده انگلیسی

Determination of the minimum number of faulty links, f(n,k)f(n,k), that make every n-kn-k-dimensional sub-star graph Sn-kSn-k faulty in an n  -dimensional star network SnSn, has been the subject of several studies. Bounds on f(n,k)f(n,k) have already been derived, and it is known that f(n,1)=n+2f(n,1)=n+2. Here, we improve the bounds on f(n,k)f(n,k). Specifically, it is shown that f(n,k)⩽(k+1)F(n,k)f(n,k)⩽(k+1)F(n,k), where F(n,k)F(n,k) is the minimum number of faulty nodes that make every Sn-kSn-k faulty in SnSn. The complexity of f(n,k)f(n,k) is shown to be O(n2k)O(n2k) which is an improvement over the previously known upper bound of O(n3)O(n3); this result in a special case leads to f(n,2)=O(n↑2)f(n,2)=O(n↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1)f(n,1) is also introduced.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 180, Issue 13, 1 July 2010, Pages 2571–2575
نویسندگان
, ,