One node fault tolerance for caterpillars and starlike trees

被引：6

作者：

Harary, F ^{[1
]}

Khurrum, M ^{[1
]}

机构：

[1] NEW MEXICO STATE UNIV,DEPT ELECT & COMP ENGN,LAS CRUCES,NM 88003

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1995年 / 56卷 / 3-4期

关键词：

caterpillar; edge cost; fault tolerance; spare node; starlike tree;

D O I：

10.1080/00207169508804394

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a given tree T with n nodes, we say that a supergraph G tolerates T (having one faulty node) if for each node u of G the subgraph G-u contains T up to isomorphism. Then G tolerates T optimally if G has just one new node and no supergraph of T with n + 1 nodes having fewer edges than G tolerates T. The one-node fault tolerance edge cost of T is the number of new edges in G. We derive theorems which determine this cost exactly for two type of trees, namely, caterpillar and starlike trees.

引用

页码：135 / 143

页数：9

共 50 条

[21] Edge-disjoint spanning trees on the star network with applications to fault tolerance
Fragopoulou, P
Akl, SG
IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (02) : 174 - 185
[22] One-fault tolerance and beyond in wormhole routed meshes
Lysne, O
Skeie, T
Waadeland, T
MICROPROCESSORS AND MICROSYSTEMS, 1998, 21 (7-8) : 471 - 480
[23] Nonlinear Control of Quadrotor for Fault Tolerance: A Total Failure of One Actuator
Wu, Yuhu
Hu, Kaijian
Sun, Xi-Ming
Ma, Yanhua
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2021, 51 (05): : 2810 - 2820
[24] Fault tolerance analysis of mesh networks with uniform versus nonuniform node failure probability
Wang, Gaocai
Wang, Guojun
Shan, Zhiguang
INFORMATION PROCESSING LETTERS, 2012, 112 (10) : 396 - 401
[25] Edges-disjoint spanning trees on the binary wrapped butterfly network with applications to fault tolerance
Touzene, A
PARALLEL COMPUTING, 2002, 28 (04) : 649 - 666
[26] Dynamic Intermediate Node Algorithm (DINA); A Novel Fault Tolerance Routing Methodology for NoC's
Aliabadi, M. R.
Khademzadeh, A.
Raiyat, M.
2008 INTERNATIONAL SYMPOSIUM ON TELECOMMUNICATIONS, VOLS 1 AND 2, 2008, : 521 - 526
[27] Central-Tapped Node Linked Modular Fault-Tolerance Topology for SRM Applications
Hu, Yihua
Gan, Chun
Cao, Wenping
Li, Wuhua
Finney, Stephen J.
IEEE TRANSACTIONS ON POWER ELECTRONICS, 2016, 31 (02) : 1541 - 1554
[28] Decentralized Latency-aware Edge Node Grouping with Fault Tolerance for Internet of Battlefield Things
Hossain, Md Sajjad
Islam, Fabliha Bushra
Nwakanma, Cosmas Ifeanyi
Lee, Jae Min
Kim, Dong-Seong
11TH INTERNATIONAL CONFERENCE ON ICT CONVERGENCE: DATA, NETWORK, AND AI IN THE AGE OF UNTACT (ICTC 2020), 2020, : 420 - 423
[29] Majorization and the spectral radius of starlike trees (vol 36, pg 121, 2018)
Oboudi, Mohammad Reza
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 130 - 130
[30] Fault Tolerance as a Service
Nandi, Bipin B.
Paul, Himadri Sekhar
Banerjee, Ansuman
Ghosh, Sasthi C.
2013 IEEE SIXTH INTERNATIONAL CONFERENCE ON CLOUD COMPUTING (CLOUD 2013), 2013, : 446 - 453

← 1 2 3 4 5 →