This paper studies four combinatorial search models of reconstructing a fixed unknown Hamiltonian cycle in the complete graph by means of queries about subgraphs. For each model, an efficient algorithm is proposed that matches asymptotically the information-theoretic lower bound. The problem is motivated by an application to genome physical mapping.
|Number of pages||8|
|Publication status||Published - 1997|
|Event||Proceedings of the 1997 5th Israel Symposium on Theory of Computing and Systems, ISTCS - Ramat-Gan, Isr|
Duration: 17 Jun 1997 → 19 Jun 1997
|Conference||Proceedings of the 1997 5th Israel Symposium on Theory of Computing and Systems, ISTCS|
|Period||17/06/97 → 19/06/97|