Edge search in hypergraphs

DOI10.1016/0012-365X(95)00291-4MaRDI QIDQ1356674zbMATH OpenFDO

Authors Ingo Althöfer, M. Löwe

Publication date 10 June 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00291-4

zbMATH Keywords

edge searchhypergraphprobability distribution

Mathematics Subject Classification ID

Hypergraphs (05C65)

Review text

Consider a hypergraph \(H=(X,E)\) with a probability distribution \(P\) on the set \(E\) of its hyperedges. The authors study the average case complexity \(\overline L(H,P)\) of finding an unknown hyperedge \(e^*\in E\), chosen according to \(P\), if allowed tests are only those that check whether \(e^*\) is contained in the induced subhypergraph \(H[Y]\) for \(Y\subset X\) or not. They show that \(H(P) \leq\overline L(H,P)\leq H(P) +3r\) where \(H(P)\) is the entropy function and \(r=\sum_{e\in E} P(e)|e|\).

Recommendations

• Edge search in graphs and hypergraphs of bounded rank
• A group testing problem for hypergraphs of bounded rank
• Searching for an edge in a graph
• Learning Theory

Cites work

• A tight upper bound for group testing in graphs
• Edge search in graphs and hypergraphs of bounded rank
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• Realizability and uniqueness in graphs
• Search problems on graphs

Cited in

(4)

• Edge search in graphs and hypergraphs of bounded rank
• A group testing problem for hypergraphs of bounded rank
• An NP-completeness result of edge search in graphs
• Edge search number of cographs

This page was built for publication: Edge search in hypergraphs

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