For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach
Toru ARAKI Yukio SHIBATA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/04/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 14th Workshop on Circuits and Systems in Karuizawa)
system-level fault diagnosis, comparison approach, butterfly network, diagnosis algorithm,
Full Text: PDF>>
In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura designed an O(n5) time diagnosis algorithm for identifying all faulty nodes in general graphs (n is the number of nodes in a system). We consider diagnosis on a butterfly network BF(k,r) and propose O(k2 n) time diagnosis algorithms for locating all faulty nodes in BF(k,r).