Reconstructing weighted graphs with minimal query complexity

DOI10.1016/j.tcs.2010.12.055zbMath1209.68267OpenAlexW2148859963MaRDI QIDQ2431425

Hanna Mazzawi, Nader H. Bshouty

Publication date: 14 April 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.12.055

zbMATH Keywords

combinatorial searchgenome sequencingreconstructing hidden graphs

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (5)

Exact learning from an honest teacher that answers membership queries ⋮ Unnamed Item ⋮ Reconstruction and verification of chordal graphs with a distance oracle ⋮ Signature codes for noisy multiple access adder channel ⋮ Network verification via routing table queries

Cites Work

• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• On a lemma of Littlewood and Offord
• Graph-Theoretic Concepts in Computer Science
• Optimal reconstruction of graphs under the additive model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reconstructing weighted graphs with minimal query complexity