Abstract
PMC model is the test-based diagnosis which a vertex performs the diagnosis by testing the neighbor vertices via the edges between them. Hsu and Tan proposed two structures to diagnose a vertex. But these structures don’t always exist for any vertex. Here, we propose a new testing structure to diagnose a vertex under PMC model to solve the problem above. It can fit more general networks. Let S be a set of faulty edges of the n-dimensional hypercube \(Q_n\). Using this structure, we show that every vertex u of \(Q_n\) is \(\deg _{Q_n-S}(u)\)-diagnosable if \(\delta (Q_n-S)\ge 2\), \(\deg _{Q_n-S}(x)+\deg _{Q_n-S}(y)\ge 5\) for every two adjacent vertices x and y in \(Q_n-S\), and \(n\ge 5\).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Armstrong, J.R., Gray, F.G.: Fault diagnosis in a Boolean \(n\)-cube array of multiprocessors. IEEE Trans. Comput. 30(8), 587–590 (1981)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)
Chang, G.-Y., Chang, G.J., Chen, G.-H.: Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16(4), 314–323 (2005)
Cull, P., Larson, S.: The Möbius cubes. IEEE Trans. Comput. 44(5), 647–659 (1995)
Dahbura, A.T., Masson, G.M.: An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. 33(6), 486–492 (1984)
EI-Awawy, A., Latifi, S.: Properties and performance of folded hypercubes. IEEE Trans. Parallel Distrib. Syst. 2(1), 31–42 (1991)
Efe, K.: The crossed cube architecture for parallel computation. IEEE Trans. Parallel Distrib. Syst. 3(5), 513–524 (1992)
Fan, J.: Diagnosability of crossed cubes under the two strategies. Chin. J. Comput. 21(5), 456–462 (1998)
Fan, J.: Diagnosability of the Möbius cubes. IEEE Trans. Parallel Distrib. Syst. 9(9), 923–928 (1998)
Harary, F., Hayes, J.P., Wu, H.-J.: A survey of the theory of hypercube graphs. Comput. Math. Appl. 15(4), 277–289 (1988)
Hilbers, P.A.J., Koopman, M.R.J., van de Snepscheut, J.L.A.: The twisted cube. In: de Bakker, J.W., Nijman, A.J., Treleaven, P.C. (eds.) PARLE 1987. LNCS, vol. 258, pp. 152–159. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-17943-7_126
Hsu, G.H., Tan, J.J.M.: A local diagnosability measure for multiprocessor systems. IEEE Trans. Parallel Distrib. Syst. 18, 598–607 (2007)
Hsu, L.-H., Lin, C.-K.: Graph Theory and Interconnection Networks. CRC Press, Boca Raton (2009)
Kavianpour, A., Kim, K.H.: Diagnosability of hypercube under the pessimistic one-step diagnosis strategy. IEEE Trans. Comput. 40(2), 232–237 (1991)
Lee, C.-W., Hsieh, S.-Y.: Diagnosability of two-matching composition networks under the MM\(^*\) model. IEEE Trans. Dependable Secure Comput. 8(2), 246–255 (2011)
Lee, C.-W., Hsieh, S.-Y.: Determining the diagnosability of \((1,2)\)-matching composition networks and its applications. IEEE Trans. Dependable Secure Comput. 8(3), 353–362 (2011)
Lai, P.-L., Tan, J.J.M., Chang, C.-P., Hsu, L.-H.: Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54(2), 165–175 (2005)
Lin, C.-K., Teng, Y.-H.: The diagnosability of triangle-free graphs. Theoret. Comput. Sci. 530, 58–65 (2014)
Lin, C.-K., Zhang, L., Fan, J., Wang, D.: Structure connectivity and substructure connectivity of hypercubes. Theoret. Comput. Sci. 634, 97–107 (2016)
Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput. 16(12), 848–854 (1967)
Saad, Y., Schultz, M.H.: Topological properties of hypercubes. IEEE Trans. Comput. 37(7), 867–872 (1988)
Wang, D.: Diagnosability of enhanced hypercubes. IEEE Trans. Comput. 43(9), 1054–1061 (1994)
Wang, G., Lin, C.-K., Fan, J., Cheng, B., Jia, X.: A novel low cost interconnection architecture based on the generalized hypercube. IEEE Trans. Parallel Distrib. Syst. 31(3), 647–662 (2020)
Acknowledgment
This work was supported by Fujian Provincial Department of Science and Technology (2020J01268).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, M., Hsu, D.F., Lin, CK. (2021). A New Measure for Locally t-Diagnosable Under PMC Model. In: Chen, CY., Hon, WK., Hung, LJ., Lee, CW. (eds) Computing and Combinatorics. COCOON 2021. Lecture Notes in Computer Science(), vol 13025. Springer, Cham. https://doi.org/10.1007/978-3-030-89543-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-89543-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89542-6
Online ISBN: 978-3-030-89543-3
eBook Packages: Computer ScienceComputer Science (R0)