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

Article type: Research Article

Authors: Lin, Cheng-Kuan^a | Kung, Tzu-Liang^b | Wang, Dajin^c | Teng, Yuan-Hsiang^{d; *}

Affiliations: [a] College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China | [b] Department of Computer Science and Information Engineering, Asia University, Taichung City, Taiwan 413, R.O.C. | [c] Department of Computer Science, Montclair State University, Upper Montclair, N.J. 07043, U.S.A. | [d] Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.. yhteng@pu.edu.tw

Correspondence: [*] Address for correspondence: Department of Computer Science and Information Engineering, Providence University, Taichung City, Taiwan 433, R.O.C.

Abstract: 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 (K4 – {e})-free graph under the PMC model.

Keywords: system diagnosis, diagnosability, PMC model

DOI: 10.3233/FI-2020-1985

Journal: Fundamenta Informaticae, vol. 177, no. 2, pp. 181-188, 2020