NP-Complete Diagnosis Problems on System Graphs

Toshihide IBARAKI; Tsunehiko KAMEDA; Shunichi TOIDA

NP-Complete Diagnosis Problems on System Graphs

Toshihide IBARAKI, Tsunehiko KAMEDA, Shunichi TOIDA

Full Text Views

0

Share
Cite this

Summary :

Various minimization problems associated with the diagnosis of systems represented by directed graphs are shown to be NP-complete. These problems include () finding the minimum number of test points, test connections and blocking gates on a SEC graph (single entry single exit connected acyclic graph), respectively, to make it distinguishable, and () finding a test set with the minimum number of tests to locate a faulty vertex on a SEC graph with test points, test connections and blocking gates attached, respectively. The NP-completeness results indicate that these problems are all intractable in the sense that it is most unlikely that some algorithm can solve them in polynomial time of the problem size.

Publication: IEICE TRANSACTIONS on transactions Vol.E62-E No.2 pp.81-88

Publication Date: 1979/02/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computers

Authors

Toshihide IBARAKI
Tsunehiko KAMEDA
Shunichi TOIDA

Keyword

Cite this

Copy

Toshihide IBARAKI, Tsunehiko KAMEDA, Shunichi TOIDA, "NP-Complete Diagnosis Problems on System Graphs" in IEICE TRANSACTIONS on transactions, vol. E62-E, no. 2, pp. 81-88, February 1979, doi: .
Abstract: Various minimization problems associated with the diagnosis of systems represented by directed graphs are shown to be NP-complete. These problems include () finding the minimum number of test points, test connections and blocking gates on a SEC graph (single entry single exit connected acyclic graph), respectively, to make it distinguishable, and () finding a test set with the minimum number of tests to locate a faulty vertex on a SEC graph with test points, test connections and blocking gates attached, respectively. The NP-completeness results indicate that these problems are all intractable in the sense that it is most unlikely that some algorithm can solve them in polynomial time of the problem size.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e62-e_2_81/_p

Copy

@ARTICLE{e62-e_2_81,
author={Toshihide IBARAKI, Tsunehiko KAMEDA, Shunichi TOIDA, },
journal={IEICE TRANSACTIONS on transactions},
title={NP-Complete Diagnosis Problems on System Graphs},
year={1979},
volume={E62-E},
number={2},
pages={81-88},
abstract={Various minimization problems associated with the diagnosis of systems represented by directed graphs are shown to be NP-complete. These problems include () finding the minimum number of test points, test connections and blocking gates on a SEC graph (single entry single exit connected acyclic graph), respectively, to make it distinguishable, and () finding a test set with the minimum number of tests to locate a faulty vertex on a SEC graph with test points, test connections and blocking gates attached, respectively. The NP-completeness results indicate that these problems are all intractable in the sense that it is most unlikely that some algorithm can solve them in polynomial time of the problem size.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - NP-Complete Diagnosis Problems on System Graphs
T2 - IEICE TRANSACTIONS on transactions
SP - 81
EP - 88
AU - Toshihide IBARAKI
AU - Tsunehiko KAMEDA
AU - Shunichi TOIDA
PY - 1979
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E62-E
IS - 2
JA - IEICE TRANSACTIONS on transactions
Y1 - February 1979
AB - Various minimization problems associated with the diagnosis of systems represented by directed graphs are shown to be NP-complete. These problems include () finding the minimum number of test points, test connections and blocking gates on a SEC graph (single entry single exit connected acyclic graph), respectively, to make it distinguishable, and () finding a test set with the minimum number of tests to locate a faulty vertex on a SEC graph with test points, test connections and blocking gates attached, respectively. The NP-completeness results indicate that these problems are all intractable in the sense that it is most unlikely that some algorithm can solve them in polynomial time of the problem size.
ER -