Journal of Combinatorial Optimization
Volume 14, Numbers 2-3, 121-129, DOI: 10.1007/s10878-007-9067-3

An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution

H. B. Chen, D. Z. Du and F. K. Hwang

From the issue entitled "Special Issue: Selected Papers from the CTS Conference on Combinatorics and its Applications in Honor of Frank K. Hwang's 65th Birthday; Guest Editors: Gerard J. Chang, Hung-Lin Fu and Xuding Zhu"

View Related Documents

Abstract

This paper discusses the relation among four problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. We prove a surprising equivalence relation among these four problems, and use this equivalence to improve current results on graph testing. In the rest of this paper, we give a lower bound for the minimum number of tests on DNA complex screening model.

Keywords  Group testing - Pooling designs - Superimposed codes - Graph testing

The first and second author would like to dedicate this paper to professor Frank K. Hwang on the occasion of his 65th birthday.
This research is partially supported by Republic of China, National Science Council grant NSC 92-2115-M-009-014.

Fulltext Preview

Image of the first page of the fulltext document