• DocumentCode
    2671980
  • Title

    The complexity of determining the sequential diagnosability number in the Malek´s comparison model

  • Author

    Liuding, Zhou ; Xiaofan, Yang ; Tinghuai, Chen ; Chenli, Tang

  • Author_Institution
    Dept. of Comput., Chongqing Univ., China
  • fYear
    1993
  • fDate
    16-18 Nov 1993
  • Firstpage
    191
  • Lastpage
    196
  • Abstract
    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|3/2 log 2(|V|)) algorithm for determining the sequential diagnosability number for a class of systems corresponding to bipartite graphs
  • Keywords
    computational complexity; fault diagnosis; graph theory; logic testing; sequential circuits; Malek´s comparison model; NP-completeness; algorithm; bipartite graphs; polynomials; sequential diagnosability number; transforms; Bipartite graph; Fault diagnosis; Large-scale systems; Multiprocessing systems; Performance evaluation; Sequential diagnosis; System testing; Variable speed drives;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Test Symposium, 1993., Proceedings of the Second Asian
  • Conference_Location
    Beijing
  • Print_ISBN
    0-8186-3930-X
  • Type

    conf

  • DOI
    10.1109/ATS.1993.398801
  • Filename
    398801
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2671980