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”, in Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, July 25–28, 2003, pages 182–191.
Consider a game in a given set of intervals (and their implied interval graph
G) in which the adversary chooses an independent set X in
G. The 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 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.
- The paper is 10 pages.
- The paper is available in PostScript (199k) and gzipped PostScript (76k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- PCR_TCS (Finding Hidden Independent Sets in Interval Graphs)
- PCR_TR2001 (Finding Hidden Independent Sets in Interval Graphs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by