Optimal query complexity for reconstructing hypergraphs

DOI10.4230/LIPICS.STACS.2010.2496MaRDI QIDQ3113744zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty, Hanna Mazzawi

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_1161.html

zbMATH Keywords

hypergraphsquery complexityreconstruction of hidden weighted hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Optimally reconstructing weighted graphs using queries
• Reconstructing weighted graphs with minimal query complexity
• Reconstructing weighted graphs with minimal query complexity
• Optimal query complexity bounds for finding graphs
• Non-adaptive learning of a hidden hypergraph

Cited in

(6)

• Weighted 2-sections and hypergraph reconstruction
• Reconstructing weighted graphs with minimal query complexity
• Exact learning from an honest teacher that answers membership queries
• Reconstructing weighted graphs with minimal query complexity
• Optimally reconstructing weighted graphs using queries
• Learning partitions using rank queries

This page was built for publication: Optimal query complexity for reconstructing hypergraphs

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