Optimally reconstructing weighted graphs using queries

MaRDI QIDQ5417652zbMATH OpenFDO

Authors Hanna Mazzawi

Publication date 22 May 2014

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Signed and weighted graphs (05C22)

Recommendations

• Reconstructing weighted graphs with minimal query complexity
• Reconstructing weighted graphs with minimal query complexity
• Optimal query complexity for reconstructing hypergraphs
• Optimal query complexity bounds for finding graphs
• Optimal reconstruction of graphs under the additive model

Cited in

(14)

• Reconstructing weighted graphs with minimal query complexity
• Algorithms that access the input via queries
• Optimal query complexity bounds for finding graphs
• Optimal query complexity for reconstructing hypergraphs
• Computing exact minimum cuts without knowing the graph
• Reconstructing weighted graphs with minimal query complexity
• Optimal reconstruction of graphs under the additive model
• Reconstruction and verification of chordal graphs with a distance oracle
• Exact learning from an honest teacher that answers membership queries
• Reconstituting beta graphs into an efficacious system
• Network verification via routing table queries
• Toward a deterministic polynomial time algorithm with optimal additive query complexity
• Reconstructing Markov processes from independent and anonymous experiments
• Toward a deterministic polynomial time algorithm with optimal additive query complexity

This page was built for publication: Optimally reconstructing weighted graphs using queries

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