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
Last updated June 7, 2021 by