A NOTE ON THE MINIMUM CUT COVER OF GRAPHS

Abstract

Loulou formulates the problem of minimizing the test time for printed circuit boards into that of minimizing the cardinality of cut cover for graphs. This note shows that the minimum cardinality of cut cover for a graph G is inverted left perpendicular log2 chi(G) inverted right perpendicular. This result enables us to conclude that the problem of determining the minimum cardinality of cut cover is NP-hard. It is also known that every planar graph is 4-colorable. Thus, if the layouts of printed circuit board form a planar graph, the minimum time needed to test the circuits is at most 2.