A New Algorithm to Determine All the Minimum Edge Sets of a System Graph

Abstract

This paper describes a new algorithm to determine all the minimum edge sets, of a given system graph, under which the graph becomes 1-distinguishable i.e., by placing suitable test points at those edges, it can be detected which of the functional blocks of the system i.e., which of the vertices of the system graph is faulty. The problem has been tackled within the framework of switching theory by introducing certain ideas of classical prime implicant covering. The algorithm is efficient, simple, straight-forward and easily programmable on a digital computer.

Indexing Terms:

• Minimum Edge Sets
• System Graphs
• SEC
• Fault Testing