ON THE FAULT-DIAMETER OF THE STAR GRAPH

被引：86

作者：

LATIFI, S

机构：

[1] Electrical and Computer Engineering Department, University of Nevada, Las Vegas, Las Vegas

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 46卷 / 03期

关键词：

DIAMETER; DISJOINT PATH; FAULT-DIAMETER; PERMUTATION; STAR GRAPH; FAULT TOLERANCE; COMBINATORIAL PROBLEMS;

D O I：

10.1016/0020-0190(93)90060-M

中图分类号：

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

学科分类号：

0812 ;

摘要：

We derive the fault-diameter of the star graph using a combinatorial method, thereby resting the previously open question of finding the exact value for the fault diameter of the star graph. This method is based on counting the number of node-disjoint paths of optimal length between a given pair of nodes in the graph and distributing the faulty nodes among these paths in a worst-case fashion. The fault-diameter for the n-star graph is shown to be D(n) + 1 for n greater-than-or-equal-to 7, where D(n) is the diameter of the fault-free star graph.

引用

页码：143 / 150

页数：8

共 7 条

[1]

Akers S. B., 1986, Proceedings of the 1986 International Conference on Parallel Processing (Cat. No.86CH2355-6), P216

[2]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[3]

AKERS SB, 1987, 2ND P INT C SUP

[4]

DAY K, 1991, 9110 U MINN DEP COMP

[5]

DAY K, IN PRESS IEEE T PARA

[6]

KRISHNAMOORTHY MS, 1987, 2ND P INT C SUP

[7] COMBINATORIAL ANALYSIS OF THE FAULT-DIAMETER OF THE N-CUBE [J].

LATIFI, S .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (01) :27-33

← 1 →