Branch-and-bound algorithms for the test cover problem

K.M.J. Bontridder, de, B.J. Lageweg, J.K. Lenstra, J.B. Orlin, L. Stougie

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

23 Citaten (Scopus)
1 Downloads (Pure)


In the test cover problem a set of items is given together with a collection of subsets of the items, called tests. A smallest subcollection 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. It 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 the problem to optimality. The variety is in the de.nition of the branching rules and the lower bounds to prune the search tree. Our algorithms are compared both theoretically and empirically.
Originele taal-2Engels
TitelAlgorithms - ESA 2002 (Proceedings 10th Annual European Symposium, Rome, Italy, September 17-21, 2002)
RedacteurenR. Möhring, R. Raman
Plaats van productieBerlin
ISBN van geprinte versie3-540-44180-8
StatusGepubliceerd - 2002

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Branch-and-bound algorithms for the test cover problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit