ALCOMFT-TR-02-79

K.M.J. De Bontridder, J.K. Lenstra, J.B. Orlin and L. Stougie
Branch and bound algorithms for the minimum test set problem
Utrecht. Work package 3. May 2002.

Abstract: In the minimum test set problem a set of items is given together with a collection of subsets of the items, called tests. A smallestset of tests is to be selected such that for every pair of items there is a test in the selection that contains exactly one of the two items. This problem is NP-hard in general. The problem has important applications in biology, pharmacy, and the medical sciences, as well as in coding theory. We develop a variety of branch and bound algorithms to solve this problem exactly. The variety is in the definition of the branching rules and the lower bounds to prune the search tree. The emerging algorithms are compared both theoretically and empirically.

Postscript file: ALCOMFT-TR-02-79.ps.gz (93 kb).