Reconstructing weighted graphs with minimal query complexity

DOI10.1016/J.TCS.2010.12.055MaRDI QIDQ2431425zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty, Hanna Mazzawi

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

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

Recommendations

• Reconstructing weighted graphs with minimal query complexity
• Optimally reconstructing weighted graphs using queries
• Optimal query complexity for reconstructing hypergraphs
• Optimal query complexity bounds for finding graphs
• Toward a deterministic polynomial time algorithm with optimal additive query complexity

Cites work

• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1222833 (Why is no real title available?)
• scientific article; zbMATH DE number 5485589 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• On a lemma of Littlewood and Offord
• Optimal reconstruction of graphs under the additive model
• Optimally reconstructing weighted graphs using queries
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

Cited in

(12)

• Reconstruction and verification of chordal graphs with a distance oracle
• Exact learning from an honest teacher that answers membership queries
• Optimal query complexity for reconstructing hypergraphs
• Reconstructing weighted graphs with minimal query complexity
• Computing exact minimum cuts without knowing the graph
• Signature codes for noisy multiple access adder channel
• Optimally reconstructing weighted graphs using queries
• Optimal reconstruction of graphs under the additive model
• Weighted microscopic image reconstruction
• Cut-query algorithms with few rounds
• Network verification via routing table queries
• Optimal query complexity bounds for finding graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431425)