Efficient Diagnosis Algorithms on Butterfly Networks under the Comparison Approach

Toru ARAKI  Yukio SHIBATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.4   pp.842-848
Publication Date: 2002/04/01
Online ISSN: 
DOI: 
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)
Category: 
Keyword: 
system-level fault diagnosis,  comparison approach,  butterfly network,  diagnosis algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
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).