loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97)
Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs
Ramat-Gan, ISRAEL
June 17-June 19
ISBN: 0-8186-8037-7
ASCII Text
x 
 
Vladimir Grebinski, Gregory Kucherov, "Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs," Theory of Computing Systems, Israel Symposium on the, pp. 166, Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), 1997.
 
 
BibTex
x
 
@article{ 10.1109/ISTCS.1997.595169,
author = {Vladimir Grebinski and Gregory Kucherov},
title = {Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs},
journal ={Theory of Computing Systems, Israel Symposium on the},
volume = {0},
year = {1997},
isbn = {0-8186-8037-7},
pages = {166},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISTCS.1997.595169},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Theory of Computing Systems, Israel Symposium on the
TI - Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs
SN - 0-8186-8037-7
SP
EP
A1 - Vladimir Grebinski,
A1 - Gregory Kucherov,
PY - 1997
VL - 0
JA - Theory of Computing Systems, Israel Symposium on the
ER -
 
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.
Citation:
Vladimir Grebinski, Gregory Kucherov, "Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs," istcs, pp.166, Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), 1997
Usage of this product signifies your acceptance of the Terms of Use.