| Article ID: | iaor20022475 |
| Country: | United States |
| Volume: | 32 |
| Issue: | 3 |
| Start Page Number: | 187 |
| End Page Number: | 197 |
| Publication Date: | Oct 1998 |
| Journal: | Networks |
| Authors: | Kahng Andrew B., Robins Gabriel, Walkup Elizabeth A. |
We address the problem of verifying that a tree is connected using probe operations which check mutual connectivity between two (or more) leaves of the tree. We present optimal algorithms for determining minimal probe sets that detect all possible edge and vertex faults in arbitrary trees. Our results are of particular interest for the testing of interconnection substrates in very large scale integration multichip module packaging technologies.