On Minimal Test Sets for Locating Single Link Failures in Networks
- 1 March 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (3) , 182-190
- https://doi.org/10.1109/tc.1981.1675754
Abstract
Consider a network which can be represented by an acyclic directed graph such that the links represented by the edges are subject to failure. Under the assumption that at most one link can fail at any time, we want to locate a failed link, if any, by means of certain tests. A test is performed by injecting a signal at a vertex and monitoring it at another vertex and can reveal if there is a failed link on any path between the two vertices. We want to find a minimal set of tests that can uniquely locate any single fault. Since this problem is in general NP-complete, we investigate a special case where the given network has a tree structure. We present an algorithm whose worst case running time can be bounded by a linear function of the input size.Keywords
This publication has 12 references indexed in Scilit:
- Minimal Test Set for Diagnosing a Tree SystemPublished by Elsevier ,1981
- A diagnosing algorithm for networksInformation and Control, 1975
- An Approach to the Diagnosability Analysis of a SystemIEEE Transactions on Computers, 1975
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- Test Point Placement to Simplify Fault DetectionIEEE Transactions on Computers, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Computer Diagnosis Using the Blocking Gate ApproachIEEE Transactions on Computers, 1971
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Distinguishability Criteria in Oriented Graphs and Their Application to Computer Diagnosis-IIEEE Transactions on Circuit Theory, 1969
- On the Connection Assignment Problem of Diagnosable SystemsIEEE Transactions on Electronic Computers, 1967