DocumentCode
2264645
Title
Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs
Author
Grebinski, Vladimir ; Kucherov, Gregory
Author_Institution
INRIA-Lorraine, Villers-les-Nancy, France
fYear
1997
fDate
17-19 Jun 1997
Firstpage
166
Lastpage
173
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
Keywords
combinatorial mathematics; search problems; Hamiltonian cycle; combinatorial search models; information-theoretic lower bound; query bounds; subgraphs; Adaptive algorithm; Bioinformatics; Blood; Communication industry; Costs; Genomics; Pollution measurement; Search problems; Software engineering; System testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location
Ramat-Gan
Print_ISBN
0-8186-8037-7
Type
conf
DOI
10.1109/ISTCS.1997.595169
Filename
595169
Link To Document