The Diagnosability of(K4 - {e})-free Graphs under the PMC Diagnosis Model

• Autorzy: Lin Cheng-Kuan , Kung Tzu-Liang , Wang Dajin , Teng Yuan-Hsiang

Identyfikatory

DOI

10.3233/FI-2020-1985

• Języki publikacji: EN

Abstrakty

EN

The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the test-based diagnosis with a processor performing the diagnosis by testing the neighboring processors via the links between them. In this paper, we discuss the diagnosability of a (K₄–{e })-free graph under the PMC model.

Słowa kluczowe

EN

system diagnosis; diagnosability; PMC model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 2
• Strony: 181--188
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Lin Cheng-Kuan

• College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China

autor

Kung Tzu-Liang

• Department of Computer Science and Information Engineering, Asia University, Taichung City, Taiwan 413, R.O.C.

autor

Wang Dajin

• Department of Computer Science, Montclair State University, Upper Montclair, N.J. 07043, U.S.A.

autor

Teng Yuan-Hsiang

• Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.

Bibliografia

• [1] Chang GY, Chang GJ, Chen GH. Diagnosabilities of regular networks, IEEE Transactions on Parallel and Distributed Systems, 2005;16:314-323. URL https://doi.org/10.1109/TPDS.2005.44.
• [2] Chang NW, Hsieh SY. Conditional diagnosability of augmented cubes under the PMC model, IEEE Transactions on Dependable and Secure Computing, 2010;9:46-60. URL https://doi.org/10.1109/TDSC.2010.59.
• [3] Chang NW, Hsieh SY. Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2014;25:3002-3011. URL https://doi.org/10.1109/TPDS.2013.290.
• [4] Dahbura AT, Masson GM. An O(n2.5) fault identification algorithm for diagnosable systems, IEEE Transactions on Computers, 1984;33:486-492. URL https://doi.org/10.1109/TC.1984.1676472.
• [5] Hakimi SL, Amin AT. Characterization of connection assignment of diagnosable systems, IEEE Transactions on Computers, 1974;23:86-88. URL https://doi.org/10.1109/T-C.1974.223782.
• [6] Hsieh SY, Chuang TY. The strong diagnosability of regular networks and product networks under the PMC model, IEEE Transactions on Parallel and Distributed Systems, 2009;20:367-378. URL https://doi.org/10.1109/TPDS.2008.99.
• [7] Hsu LH, Lin CK. Graph Theory and Interconnection Networks, CRC Press, 2008. ISBN-13:9781420044812.
• [8] Lin CK, Teng YH. The diagnosability of triangle-free graphs, Theoretical Computer Science, 2014;530:58-65. https://doi.org/10.1016/j.tcs.2014.02.024.
• [9] Lin L, Zhou S, Xu L, Wang D. The extra connectivity and conditional diagnosability of alternating group networks, IEEE Transactions on Parallel and Distributed Systems, 2015;26:2352-2362. https://doi.org/10.1109/TPDS.2014.2347961.
• [10] Preparata FP, Metze G, Chien RT. On the connection assignment problem of diagnosis systems, IEEE Transactions on Electronic Computers, 1967;16:848-854. https://doi.org/10.1109/PGEC.1967.264748.
• [11] Teng YH, Lin CK. A test round controllable local diagnosis algorithm under the PMC diagnosis model, Applied Mathematics and Computation, 2014;244:613-623. https://doi.org/10.1016/j.amc.2014.07.036.
• [12] Yuan J, Liu A, Ma X, Liu X. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM model, IEEE Transactions on Parallel and Distributed Systems, 2015;26:1165-1177. https://doi.org/10.1109/TPDS.2014.2318305.
• [13] Zhou S, Lin L, Xu L, Wang D. The t/k-diagnosability of star graph networks, IEEE Transactions on Computers, 2015;64:547-555. https://doi.org/10.1109/TC.2013.228.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).