کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
391860 662016 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fault-tolerant cycle embedding in the faulty hypercubes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Fault-tolerant cycle embedding in the faulty hypercubes
چکیده انگلیسی

The hypercube is one of the best known interconnection networks. Embedding cycles of all possible lengths in faulty hypercubes has received much attention. Let Fv (respectively, Fe) denote the set of faulty vertices (respectively, faulty edges) and fv (respectively, fe) denote the number of faulty vertices (respectively, faulty edge) in an n-dimensional hypercube Qn. Let f(e) denote the number of faulty nodes and/or faulty edges incident with the end-vertices of an edge e ∈ E(Qn). In this paper, we assume that each node is incident with at least three fault-free neighbors and at least three fault-free edges. Under this assumption, we show that every fault-free edge lies on a fault-free cycle of every even length from 4 to 2n − 2∣Fv∣ if ∣Fv∣ + ∣Fe∣ ⩽ 2n − 7 and f(e) ⩽ n − 2, where n ⩾ 5. Under our condition, our result not only improves the previously best known result of Hsieh et al. [S.-Y. Hsieh, T.-H. Shen, Edge-bipancyclicity of a hypercube with faulty vertices and edges, Discrete Applied Mathematics 156 (10) (2008) 1802–1808] where fv + fe ⩽ n − 2 was assumed, but also extends the result of Tsai [C.-H. Tsai, Linear array and ring embedding in conditional faulty hypercubes, Theoretical Computer Science 314 (3) (2004) 431–443] where only the faulty edges were considered and Tsai [C.-H. Tsai, Cycle embedding in hypercubes with node failures, Information Processing Letters 102 (6) (2007) 242–246] where only the faulty vertices were considered.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 253, 20 December 2013, Pages 157–162
نویسندگان
, ,