Frontiers of Mathematics in China >
g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model
Received date: 24 Oct 2015
Accepted date: 25 Jul 2017
Published date: 30 Sep 2017
Copyright
Diagnosability of a multiprocessor system is an important study topic. S. L. Peng, C. K. Lin, J. J. M. Tan, and L. H. Hsu [Appl. Math. Comput., 2012, 218(21): 10406–10412] proposed a new measure for fault diagnosis of the system, which is called the g-good-neighbor conditional diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topological structure of interconnection networks, the n-dimensional star graph Sn has many good properties. In this paper, we establish the g-good-neighbor conditional diagnosability of Sn under the PMC model and MM∗ model.
Key words： Interconnection network; graph; diagnosability; PMC model; MM∗ model; star graph
Shiying WANG , Zhenhua WANG , Mujiangshan WANG , Weiping HAN . g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model[J]. Frontiers of Mathematics in China, 2017 , 12(5) : 1221 -1234 . DOI: 10.1007/s11464-017-0657-9
| 1 |
AkersS B, KrishnamurthyB. A group-theoretic model for symmetric interconnection networks. IEEE Trans Comput, 1989, 38(4): 555–566
|
| 2 |
BondyJ A, MurtyU S R. Graph Theory. New York: Springer, 2007
|
| 3 |
ChangN W, HsiehS Y. Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Trans Parallel Distrib Syst, 2014, 25(11): 3002–3011
|
| 4 |
DahburaA T, MassonG M. An O(n2.5) fault identification algorithm for diagnosable systems. IEEE Trans Comput, 1984, 33(6): 486–492
|
| 5 |
DayK, TriphthiA. A comparative study of topological properties of hypercubes and star graphs. IEEE Trans Parallel Distrib Syst, 1994, 5(1): 31–38
|
| 6 |
HakimiS L, AminA T. Characterization of the connection assignment of diagnosable systems. IEEE Trans Comput, 1974, C-23: 86–88
|
| 7 |
HsiehS Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoret Comput Sci, 2005, 337(1-3): 370–378
|
| 8 |
HuS C, YangC B. Fault tolerance on star graphs. In: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis. 1995, 176–182
|
| 9 |
HuangC W, HuangH L, HsiehS Y.Edge-bipancyclicity of star graphs with faulty elements. Theoret Comput Sci, 2011, 412: 6938–6947
|
| 10 |
HungerfordW H. Algebra. New York: Springer-Verlag, 1974
|
| 11 |
LaiP L, TanJ J M, ChangC P, HsuL H. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput, 2005, 54(2): 165–175
|
| 12 |
LatifiS. A study of fault tolerance in star graph. Inform Process Lett, 2007, 102(5): 196–200
|
| 13 |
LatifiS, SaberiniaE, WuX. Robustness of star graph network under link failure. Inform Sci, 2008, 178(3): 802–806
|
| 14 |
LiT K, TanJ J M, HsuL H. Hyper Hamiltonian laceability on edge fault star graph. Inform Sci, 2004, 165(1-2): 59–71
|
| 15 |
LiX J, XuJ M. Generalized measures for fault tolerance of star networks. Networks, 2014, 63(3): 225–230
|
| 16 |
LiX Y, FanJ, LinC K, JiaX. Diagnosability evaluation of the data center network DCell. Comput J, 2017, 1–15,
|
| 17 |
LinC K, TanJ J M, HsuL H, ChengE, Lipt´aakL. Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J Inter Net, 2008, 9(1-2): 83–97
|
| 18 |
MaengJ, MalekM. A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceeding of 11th International Symposium on Fault-Tolerant Computing. 1981, 173–175
|
| 19 |
PengS L, LinCK, TanJ J M, HsuLH. The g-good-neighbor conditional diagnosability of hypercube under PMC model. Appl Math Comput, 2012, 218(21): 10406–10412
|
| 20 |
PretarataF P, MetzeG, ChienR T. On the connection assignment problem of diagnosable systems. IEEE Trans Comput, 1967, EC-16(6): 848–854
|
| 21 |
RescignoA A. Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security. Inform Sci, 2001, 137(1-4): 259–276
|
| 22 |
TsaiP Y, FuJ S, ChenJ H. Fault-free longest paths in star networks with conditional link faults. Theoret Comput Sci, 2009, 410(8-10): 766–775
|
| 23 |
WalkerD, LatifiS. Improving bounds on link failure tolerance of the star graph. Inform Sci, 2010, 180(13): 2571–2575
|
| 24 |
WanM, ZhangZ. A kind of conditional vertex connectivity of star graphs. Appl Math Lett, 2009, 22(2): 264–267
|
| 25 |
WangM, YangW, GuoY, WangS. Conditional fault tolerance in a class of Cayley graphs. Int J Comput Math, 2016, 93(1): 67–82
|
| 26 |
WangS, HanW. The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM∗ model. Inform Process Lett, 2016, 116: 574–577
|
| 27 |
WangX, FanJ, ZhouJ, LinC K. The restricted h-connectivity of the data center network DCell. Discrete Appl Math, 2016, 203: 144–157
|
| 28 |
YangY, WangS. Conditional connectivity of star graph networks under embedding restriction. Inform Sci, 2012, 199: 187–192
|
| 29 |
YuanJ, LiuA, MaX, LiuX, QinX, ZhangJ. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM∗ model. IEEE Trans Parallel Distrib Syst, 2015, 26: 1165–1177
|
| 30 |
ZhengJ, LatifiS, RegentovaE, LuoK, WuX. Diagnosability of star graphs under the comparison diagnosis model. Inform Process Lett, 2005, 93(1): 29–36
|
| 31 |
ZhouS, LinL, XuL, WangD. The t/k-diagnosability of star graph networks. IEEE Trans Comput, 2015, 64(2): 547–555
|
| 32 |
ZhouS, XuJ M. Fault diagnosability of arrangement graphs. Inform Sci, 2013, 246: 177–190
|
/
| 〈 |
|
〉 |