HOW TO TEST A TREE

We address the problem of verifying that a tree is connected using pro be operations which check mutual connectivity between two (or more) le aves of the tree. We present optimal algorithms for determining minima l probe sets that detect all possible edge and vertex faults in arbitr ary trees. Our results are of particular interest for the testing of i nterconnection substrates in VLSI multichip module packaging technolog ies. (C) 1998 John Wiley & Sons, Inc.