A note on the minimum cut cover of graphs

A note on the minimum cut cover of graphs

0.00 Avg rating0 Votes
Article ID: iaor19951460
Country: Netherlands
Volume: 15
Issue: 4
Start Page Number: 193
End Page Number: 194
Publication Date: Apr 1994
Journal: Operations Research Letters
Authors: ,
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 ⌈log2&chi(G)⌉. 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.

Reviews

Required fields are marked *. Your email address will not be published.