Therese Biedl, Brona Brejova, Erik D. Demaine, Angele M. Hamel, Alejandro Lopez-Ortiz, Tomas Vinar. Finding Hidden Independent Sets in Interval Graphs. Theoretical Computer Science, 310(1-3):287-307. January 2004. Early version appeared in COCOON 2003.

Download preprint: 04pcr.pdf, 216Kb

Download from publisher: http://dx.doi.org/10.1016/S0304-3975(03)00422-5

Related www page: not available

Bibliography entry: BibTeX

See also: early version

Abstract:

We design efficient competitive algorithms for discovering hidden information 
using few queries. Specifically, consider a game in a given set of intervals 
(and their implied interval graph G) in which our goal is to discover an 
(unknown) independent set X by making the fewest queries of the form "Is 
point p covered by an interval in X?" Our interest in this problem stems from 
two applications: experimental gene discovery with PCR technology and the 
game of Battleship (in a 1-dimensional setting). We provide adaptive 
algorithms for both the verification scenario (given an independent set, is 
it X?) and the discovery scenario (find X without any information). Under 
some assumptions, these algorithms use an asymptotically optimal number of 
queries in every instance.

Last update: 10/01/2006