Minimal cut cover of a graph with an application to the testing of electronic boards

One type of testing for short circuits in printed circuit boards components is described and modelled as the covering of the edges of a graph by cuts. To minimize testing time then amounts to minimize the number of cuts that cover all edges. The main result of this article is to find the minimum cardinality cut cover of a complete graph via an O(nlogn) algorithm. The cardinality is shown to be equal to ⌈log2n⌉. For a general graph, the same procedure produces a good heuristic edge cover with ‘nice’ properties.