Edge search in hypergraphs
type: Item
instance of: scholarly article
title: Edge search in hypergraphs
zbMATH Open document ID: 0874.05040
DOI: 10.1016/0012-365X(95)00291-4
author: Ingo Althöfer
author: M. Löwe
published in: Discrete Mathematics
publication date: 1997-06-10T00:00:00Z
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|\).
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1019035
zbMATH Keywords: edge search
zbMATH Keywords: hypergraph
zbMATH Keywords: probability distribution
reviewed by: Du Ding-Zhu
MaRDI profile type: Publication
cites work: Search problems on graphs
cites work: Q3994535
cites work: Realizability and uniqueness in graphs
cites work: Q3792452
cites work: Edge search in graphs and hypergraphs of bounded rank
cites work: Q4198785
cites work: A tight upper bound for group testing in graphs
cites work: Q4857782
description: scientific article; zbMATH DE number 1019035