Paper by Erik D. Demaine

Therese Biedl, Broňa Brejová, Erik D. Demaine, Angèle M. Hamel, Alejandro López-Ortiz, and Tomáš Vinař, “Finding Hidden Independent Sets in Interval Graphs”, Technical Report 2001-26, Department of Computer Science, University of Waterloo, December 2001.

We design efficient competitive algorithms for discovering information hidden by an adversary. Specifically, consider a game in a given interval graph G in which the adversary chooses an independent set X in G. Our goal is to discover this hidden 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 on the interval graph, these algorithms use an asymptotically optimal number of queries in every instance.

The paper is 21 pages.

The paper is available in PostScript (294k) and gzipped PostScript (112k).
See information on file formats.
[Google Scholar search]

Related papers:
PCR_TCS (Finding Hidden Independent Sets in Interval Graphs)
PCR_COCOON2003 (Finding Hidden Independent Sets in Interval Graphs)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 26, 2017 by Erik Demaine.