Printed Circuit Board Testing II - Clique
Next: Pattern Matching
Up: Sample Applications
Previous: Printed Circuit Board
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