کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657868 | 690575 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Embedding longest fault-free paths onto star graphs with more vertex faults
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Embedding longest fault-free paths onto star graphs with more vertex faults Embedding longest fault-free paths onto star graphs with more vertex faults](/preview/png/9657868.png)
چکیده انگلیسی
The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is recognized as an attractive alternative to the hypercube. Since S1,S2, and S3 have trivial structures, we focus our attention on Sn with n⩾4 in this paper. Let F(Sn) be the set of vertex faults. Previously, it was shown that when |F(Sn)|⩽n-5, Sn with n⩾6 can embed a longest fault-free path of length at least n!-2|F(Sn)|-1 (respectively, n!-2|F(Sn)|-2) between two arbitrary vertices in different partite sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults, Theoretical Computer Science 262 (2001) 215-227]. In this paper, we improve the above result by tolerating more faults (|F(Sn)|⩽n-3) to embed a longest fault-free path between two arbitrary vertices in Sn, n⩾4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 337, Issues 1â3, 9 June 2005, Pages 370-378
Journal: Theoretical Computer Science - Volume 337, Issues 1â3, 9 June 2005, Pages 370-378
نویسندگان
Sun-Yuan Hsieh,