Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs
Vladimir Grebinski, Grégory Kucherov · 2002
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.