Edge search in graphs and hypergraphs of bounded rank

DOI10.1016/0012-365X(93)90473-7MaRDI QIDQ1801680zbMATH OpenFDO

Authors Ingo Althöfer, Eberhard Triesch

Publication date 20 June 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90473-7

zbMATH Keywords

hypergraphstestsworst-case complexity

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (05C99) Searching and sorting (68P10)

Recommendations

• Edge search in hypergraphs
• Edge search in graphs with restricted test sets
• A group testing problem for hypergraphs of bounded rank
• Searching for an edge in a graph
• A binary search problem on graphs

Cites work

• A Group Testing Problem on Two Disjoint Sets
• A search problem on graphs which generalizes some group testing problems with two defectives
• Group testing with two defectives
• 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?)
• Search problems on graphs

Cited in

(14)

• A binary search problem on graphs
• Realizability and uniqueness in graphs
• A parallel algorithm for nearly optimal edge search
• Edge search in hypergraphs
• Edge ranking of graphs is hard
• A group testing problem for hypergraphs of bounded rank
• An NP-completeness result of edge search in graphs
• Group testing in graphs
• Edge search number of cographs
• Optimal edge ranking of complete bipartite graphs in polynomial time
• Searching for an edge in a graph
• Searching for faulty leaves in binary trees
• Searching for an edge in a graph
• A competitive algorithm in searching for many edges in a hypergraph

This page was built for publication: Edge search in graphs and hypergraphs of bounded rank

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