Search problems on graphs

DOI10.1016/0166-218X(86)90026-0zbMath0602.68052MaRDI QIDQ1082080

Martin Aigner

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

bipartite graphscomplete graphssearch theorygroup tests

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

Related Items (18)

An optimal group testing algorithm on \(k\) disjoint sets ⋮ Determining defectives in a linear order ⋮ A ternary search problem on two disjoint sets ⋮ Realizability and uniqueness in graphs ⋮ Search problems: One, two or many rounds ⋮ Edge search in hypergraphs ⋮ A ternary search problem on graphs ⋮ A search problem on graphs which generalizes some group testing problems with two defectives ⋮ A binary search problem on graphs ⋮ An adaptive algorithm for group testing for complexes ⋮ An improved algorithm for quantitative group testing ⋮ Group testing in graphs ⋮ A competitive algorithm to find all defective edges in a graph ⋮ Optimal quantitative group testing on cycles and paths ⋮ Edge search in graphs and hypergraphs of bounded rank ⋮ The optimal procedures for quantitative group testing ⋮ On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$ ⋮ A tight upper bound for group testing in graphs

Cites Work

• Group testing with two defectives
• Parallel concepts in graph theory
• On \(B_ 2\)-sequences of vectors
• On the Detection of Defective Members of Large Populations
• A Group Testing Problem on Two Disjoint Sets
• Determination of two vectors from the sum
• Determination of a Subset from Certain Combinatorial Properties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Search problems on graphs