- 期刊
- OpenAccess
A Fault-Tolerant Reconfiguration Scheme in the Faulty Star Graph
並列摘要
In this paper, we propose a scheme to identify the maximal fault-free substar-ring. This is the first attempt to derive a reconfiguration scheme with high processor utilization in the faulty n-star graph. The maximal fault-free substar-ring is connected by a ring of fault-free virtual substars and the maximal length of the ring is n(n-1)(n-2). Our proposed scheme can tolerate n-3 faults such that the processor utilization is (The equation is abbreviated). This is a near optimal result since the maximal fault-free substar-ring is constructed using all of the possible fault-free (n-2)-substars. Moreover, our algorithm can still work when the number of faults exceeds n-3. The simulation results also show that the processor utilization is more than 50% if the number of faults is less than (The equation is abbreviated) in the n-star graph.
延伸閱讀
- Kırlangıc, A., & Turan, G. B. (2012). ON THE RUPTURE DEGREE OF A GRAPH. Neural Network World, 22(1), 39-51. https://doi.org/10.14311/NNW.2012.22.003
- Kao, K. H. (2010). The Next-to-Shortest Path Problem in Graphs [doctoral dissertation, National Chi Nan University]. Airiti Library. https://doi.org/10.6837/NCNU.2010.00188
- Liu, Y. Z. (2019). A Study on the Decycling Number of Bubble-sort Star Graphs [master's thesis, National Taipei University of Business]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0064-2505202011274333
- Law, K. H. (2010). Some results in graph theory [doctoral dissertation, The University of Hong Kong]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0029-1812201200017581
- Zhao, Q., Luo, P., & Xi, Q. (2015). Local Structure Recovery of Chain Graphs after Marginalization. Discrete Dynamics in Nature and Society, 2015(), 600-604-362. https://doi.org/10.1155/2015/982495