Efficient diagnosis algorithms on butterfly networks under the comparison approach
In this paper, we study system-level diagnosis under the comparison approach proposed by Maeng and Malek, Sengupta and Dahbura designed an O(n(5)) 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(k(2)n) time diagnosis algorithms for locating all faulty nodes in BF(k, r).
diagnosis algorithm butterfly network comparison approach system-level fault diagnosis