A diagnosing algorithm for networks

Consider a network G of n units, each of which can be tested by those units from which there is a test connection. The outcome of each test is binary (good or faulty) and is the judgment of the testing unit on the tested unit. We present an algorithm for identifying the minimum number of faulty unit...

Full description

Saved in:
Bibliographic Details
Published in:Information and control 1975-01, Vol.29 (2), p.141-148
Main Authors: Kameda, T., Toida, S., Allan, F.J.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a network G of n units, each of which can be tested by those units from which there is a test connection. The outcome of each test is binary (good or faulty) and is the judgment of the testing unit on the tested unit. We present an algorithm for identifying the minimum number of faulty units based on the test outcomes. It works in time proportional to τ( G) m, provided the number of faulty units is no more than τ( G), where m is the number of test connections and τ( G) is a parameter of G such that if the number of faulty units is no more than τ( G), then they are uniquely identifiable.
ISSN:0019-9958
1878-2981
DOI:10.1016/S0019-9958(75)90508-2