Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

DOI10.1016/S0166-218X(98)00070-5zbMath0936.68107MaRDI QIDQ1281767

Gregory Kucherov, Vladimir Grebinski

Publication date: 20 June 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

mathematical modelsmultiplex PCR method

Mathematics Subject Classification ID

Related Items (27)

Exact learning from an honest teacher that answers membership queries ⋮ Learning Boolean halfspaces with small weights from membership queries ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Unnamed Item ⋮ Reconstructing weighted graphs with minimal query complexity ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Learning and Verifying Graphs Using Queries with a Focus on Edge Counting ⋮ Learning a hidden graph ⋮ Reconstruction and verification of chordal graphs with a distance oracle ⋮ Developing a new approach for (biological) optimal control problems: application to optimization of laccase production with a comparison between response surface methodology and novel geometric procedure ⋮ An upper bound of the number of tests in pooling designs for the error-tolerant complex model ⋮ The Hamiltonian properties of supergrid graphs ⋮ An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution ⋮ Learning a hidden uniform hypergraph ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Network construction with subgraph connectivity constraints ⋮ Reconstruction of hidden graphs and threshold group testing ⋮ Optimal query complexity bounds for finding graphs ⋮ Nonadaptive algorithms for threshold group testing ⋮ Toward a deterministic polynomial time algorithm with optimal additive query complexity ⋮ Reconstructing Weighted Graphs with Minimal Query Complexity ⋮ Unnamed Item ⋮ Non-adaptive Learning of a Hidden Hypergraph ⋮ On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$ ⋮ Chinese remainder encoding for Hamiltonian cycles

Cites Work

• On a packing and covering problem
• Kolmogorov complexity arguments in combinatorics
• On a Combinatorial Problem in Number Theory
• Determination of two vectors from the sum
• Determination of a Subset from Certain Combinatorial Properties
• On the difference between consecutive primes
• Optimal reconstruction of graphs under the additive model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping