Paper by Erik D. Demaine
- Reference:
- 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.
- Abstract:
-
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.
- Length:
- The paper is 10 pages.
- Availability:
- 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
BibTeX file.
Last updated November 27, 2024 by
Erik Demaine.