Reconstructing weighted graphs with minimal query complexity

DOI10.1007/978-3-642-04414-4_12MaRDI QIDQ3648745zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty, Hanna Mazzawi

Publication date 1 December 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04414-4_12

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational learning theory (68Q32)

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 5957397 (Why is no real title available?)
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 1222833 (Why is no real title available?)
• scientific article; zbMATH DE number 823957 (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?)
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Learning Theory
• 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

(9)

• Reconstructing weighted graphs with minimal query complexity
• Optimal query complexity for reconstructing hypergraphs
• On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$
• Optimally reconstructing weighted graphs using queries
• Optimal reconstruction of graphs under the additive model
• Optimal reconstruction of graphs under the additive model
• Weighted microscopic image reconstruction
• Toward a deterministic polynomial time algorithm with optimal additive query complexity
• 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 Q3648745)