SEQUENTIAL DIAGNOSABILITY IS CO-NP COMPLETE

被引：18
作者：
RAGHAVAN, V [1 ]
TRIPATHI, A [1 ]
机构：
[1] UNIV MINNESOTA,DEPT COMP SCI,MINNEAPOLIS,MN 55455
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1991年 / 40卷 / 05期
关键词：
FAULT DIAGNOSIS; NP-COMPLETENESS; PMC AND BGM MODELS FOR SYSTEM DIAGNOSABILITY; SEQUENTIAL DIAGNOSABILITY;
D O I：
10.1109/12.88482
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The question of determining the sequential diagnosability number of system in the PMC model has remained open since it was first formulated two decades ago. We show that this problem is co-NP complete. The problem is also shown to be co-NP complete even when restricted to planar graphs both in the weighted and the BGM models.
引用
收藏
页码：584 / 595
页数：12
相关论文
共 26 条
[1]  
BARSI F, 1976, IEEE T COMPUT, V25, P585, DOI 10.1109/TC.1976.1674658
[2]   SCHEMES FOR FAULT-TOLERANT COMPUTING - A COMPARISON OF MODULARLY REDUNDANT AND T-DIAGNOSABLE SYSTEMS [J].
CHWA, KY ;
HAKIMI, SL .
INFORMATION AND CONTROL, 1981, 49 (03) :212-238
[3]  
CIOMPI P, 1979, IEEE T COMPUT, V28, P362, DOI 10.1109/TC.1979.1675366
[4]  
CIOMPI P, 1974, 3RD P TEX C COMP SYS, P931
[5]  
DAHBURA AT, 1987, P PRINCETON WORKSHOP
[6]  
FUJIWARA H, 1978, IEEE T COMPUT, V27, P881, DOI 10.1109/TC.1978.1674966
[7]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[8]   RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].
GAREY, MR ;
JOHNSON, DS .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834
[9]  
GAREY MR, 1978, J ACM, P499
[10]  
Karp R.M., 1972, COMPLEXITY COMPUTER, P85
123