Printed Circuit Board Testing II - Clique



next up previous
Next: Pattern Matching Up: Sample Applications Previous: Printed Circuit Board

Printed Circuit Board Testing II - Clique

A printed circuit board tester involves placing probes onto a board. A probe can determine if a portion of a board is working correctly. Since probes have a particular size, not every component can be checked in one pass. The problem of maximizing the number of components checked in one pass can be formulated as a clique problem: each node represents a component and an edge represents two nodes that are sufficiently far apart to be checked simultaneously. A clique in this graph is then a set of components that can be checked in one pass. This is an example of a geometric clique problem and has been studied by Yu, Goldschmidt and Chen [86] and Yu. Kouvelis, and Luo [87].



Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994