Search problems on graphs
The following search problem on graphs is studied: given a graph \(G=(V,E)\) and an unknown edge \(e\in E\), we can test whether a subset \(A\leq V\) contains both ends of e, one end, or neither. The edge e is to be located with the minimum number of tests. When G is a complete graph, this is a classical problem of finding defectives in a population when at most two defectives are present. Lower and upper bounds for the minimum number of tests are derived for complete graphs and for complete bipartite graphs. These give the exact values for \(K_{m,n}\), \(1\leq m\leq 4\).
- A Group Testing Problem on Two Disjoint Sets
- Determination of a Subset from Certain Combinatorial Properties
- Determination of two vectors from the sum
- Group testing with two defectives
- scientific article; zbMATH DE number 3662840 (Why is no real title available?)
- scientific article; zbMATH DE number 3532378 (Why is no real title available?)
- scientific article; zbMATH DE number 3431965 (Why is no real title available?)
- scientific article; zbMATH DE number 3264611 (Why is no real title available?)
- On \(B_ 2\)-sequences of vectors
- On the Detection of Defective Members of Large Populations
- Parallel concepts in graph theory
- Edge search in graphs with restricted test sets
- Determining defectives in a linear order
- 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 improved algorithm for quantitative group testing
- A tight upper bound for group testing in graphs
- Realizability and uniqueness in graphs
- Search problems: One, two or many rounds
- Edge search in hypergraphs
- Binary search and recursive graph problems
- A ternary search problem on two disjoint sets
- Graph extremities defined by search algorithms
- Edge search in graphs and hypergraphs of bounded rank
- The optimal procedures for quantitative group testing
- An optimal group testing algorithm on \(k\) disjoint sets
- Group testing in graphs
- A competitive algorithm to find all defective edges in a graph
- Graph Searching in a Crime Wave
- scientific article; zbMATH DE number 5726869 (Why is no real title available?)
- scientific article; zbMATH DE number 5734730 (Why is no real title available?)
- AND/OR graph heuristic search methods
- The complexity of searching a graph
- Fast-mixed searching and related problems on graphs
- scientific article; zbMATH DE number 15129 (Why is no real title available?)
- scientific article; zbMATH DE number 33703 (Why is no real title available?)
- scientific article; zbMATH DE number 1738544 (Why is no real title available?)
- scientific article; zbMATH DE number 3997549 (Why is no real title available?)
- scientific article; zbMATH DE number 749657 (Why is no real title available?)
- On a combinatorial search problem
- scientific article; zbMATH DE number 2097449 (Why is no real title available?)
- Search problems in vector spaces
- An adaptive algorithm for group testing for complexes
- Unbounded search and recursive graph problems
- On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$
- Graph Searching with Advice
- scientific article; zbMATH DE number 2220912 (Why is no real title available?)
- Searching for an edge in a graph
- Optimal quantitative group testing on cycles and paths
- A general label search to investigate classical graph search algorithms
- Some problems of the search on graphs with retaliation
This page was built for publication: Search problems on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082080)
