Embedding a ring in a hypercube with both faulty links and faulty nodes

被引：43

作者：

Tseng, YC

机构：

[1] Dept. of Comp. Sci. and Info. Eng., National Central University, Chung-Li

来源：

INFORMATION PROCESSING LETTERS | 1996年 / 59卷 / 04期

关键词：

fault tolerance; graph embedding; hypercube; interconnection network; parallel processing; ring;

D O I：

10.1016/0020-0190(96)00114-7

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we show that given a binary n-cube with f(e) less than or equal to n - 4 faulty edges and f(v) less than or equal to n - 1 faulty vertices such that f(e) + f(v) less than or equal to n - 1, a ring of length at least 2(n) - 2f(v) can be obtained. The best known results can tolerate only faulty edges or only faulty vertices.

引用

页码：217 / 222

页数：6

共 14 条

[1]

BOKHARI SH, 1981, IEEE T COMPUT, V30, P207, DOI 10.1109/TC.1981.1675756

[2] FAULT-TOLERANT EMBEDDING OF COMPLETE BINARY-TREES IN HYPERCUBES [J].