Some Completeness Results on Decision Trees and Group Testing

DOI10.1137/0608062MaRDI QIDQ3801062zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

Cited in

(9)

• 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
• On the optimal nested ordered algorithm
• 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)