The complexity of determining the sequential diagnosability number in the Malek's comparison model
Zhou Liuding, Xiaofan Yang, Tinghuai Chen, Tang Chenli · 2002
The problem of determining the sequential diagnosability number of a system in the Malek's comparison model is an important one. In this paper, we show that the decision version of this problem is co-NP complete for general systems, and we present an O(|E| |V|/sup 3/2/ log /sub 2/(|V|)) algorithm for determining the sequential diagnosability number for a class of systems corresponding to bipartite graphs.>