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”, Technical Report 2001-26, Department of Computer Science, University of Waterloo, December 2001.

BibTeX

@TechReport{PCR_TR2001,
  AUTHOR        = {Therese Biedl and Bro\v{n}a Brejov\'a and Erik D. Demaine
                   and Ang\`ele M. Hamel and Alejandro L\'opez-Ortiz and
                   Tom\'a\v{s} Vina\v{r}},
  TITLE         = {Finding Hidden Independent Sets in Interval Graphs},
  INSTITUTION   = {Department of Computer Science, University of Waterloo},
  NUMBER        = {2001-26},
  MONTH         = {December},
  YEAR          = 2001,

  length        = {21 pages},
  papers        = {PCR_TCS; PCR_COCOON2003},
}

Abstract:

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.

Length:

The paper is 21 pages.

Availability:

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)