Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs

Vladimir Grebinski, Gregory Kucherov

Research output: Contribution to conferencePaperpeer-review

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages166-173
Number of pages8
Publication statusPublished - 1997
Externally publishedYes
EventProceedings of the 1997 5th Israel Symposium on Theory of Computing and Systems, ISTCS - Ramat-Gan, Isr
Duration: 17 Jun 199719 Jun 1997

Conference

ConferenceProceedings of the 1997 5th Israel Symposium on Theory of Computing and Systems, ISTCS
CityRamat-Gan, Isr
Period17/06/9719/06/97

Fingerprint

Dive into the research topics of 'Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs'. Together they form a unique fingerprint.

Cite this