Some Completeness Results on Decision Trees and Group Testing

DOI10.1137/0608062zbMath0654.68036OpenAlexW1996086711MaRDI QIDQ3801062

Ding-Zhu Du, Ker-I. Ko

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/cc5bbc02db752abb2cadea0578a0225f1af8fbd3

zbMATH Keywords

NP-completenessdecision treegroup testing{\#}P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (6)

Search problems: One, two or many rounds ⋮ The complexity of determinacy problem on group testing ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ On optimal nested group testing algorithms ⋮ Optimal Binomial Group Testing with a Test History ⋮ Revisiting Nested Group Testing Procedures: New Results, Comparisons, and Robustness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Bounds for packet transmission rate in a random-multiple-access system
• A Note on Sparse Complete Sets
• Three Versions of a Group Testing Game
• On the Detection of Defective Members of Large Populations
• A Study of the Group Screening Method
• The Information-Theoretic Bound is Good for Merging
• Generalized Binary Binomial Group Testing
• On the number of queries necessary to identify a permutation
• Cutoff points for roll call protocols in multiple access systems
• Hypergeometric and Generalized Hypergeometric Group Testing
• A Combinatorial Problem Which Is Complete in Polynomial Space
• The Ford-Johnson Sorting Algorithm Is Not Optimal
• On a Combinatorial Problem in Number Theory
• The complexity of satisfiability problems
• Determination of a Subset from Certain Combinatorial Properties
• Optimal Binary Identification Procedures

This page was built for publication: Some Completeness Results on Decision Trees and Group Testing