Some Completeness Results on Decision Trees and Group Testing

DOI10.1137/0608062zbMATH Open0654.68036OpenAlexW1996086711MaRDI QIDQ3801062FDOQ3801062

Authors: Du Ding-Zhu, 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

Recommendations

• scientific article; zbMATH DE number 25604
• Publication:4506360
• The complexity of determinacy problem on group testing
• scientific article
• On the hardness of the minimum height decision tree problem

zbMATH Keywords

decision treeNP-completenessgroup testing{\#}P-completeness

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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

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