Printed Circuit Board Testing I - Coloring
Next: Printed Circuit Board
Up: Sample Applications
Previous: Register Allocation
Garey, Johnson,
and So [39] consider the problem of testing printed circuit boards
for unintended short circuits (caused by stray lines of solder). This gives
rise to a graph coloring problem in which the vertices correspond to the nets
on board and there is an edge between two vertices if there is a potential
for a short circuit between the corresponding nets. Coloring the graph
corresponds to partitioning the nets into ``supernets,'' where the nets
in each supernet can be simultaneously tested for shorts against all
other nets, thereby speeding up the testing process.
Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994