Minimum average-case queries of \(q+1\)-ary search game with small sets

DOI10.1016/j.dam.2011.10.030zbMath1237.91063OpenAlexW2003386477MaRDI QIDQ412374

Yang Yang, Gyula O. H. Katona, Wen An Liu, Chuang Lin, Kun Meng

Publication date: 4 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.030

zbMATH Keywords

sequential algorithmHuffman treeaverage-costsearch game

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial games (91A46)

Related Items

Minimum number of queries for an adaptive liar search game with small sets ⋮ Disjoint Spread Systems and Fault Location

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On separating systems whose elements are sets of at most k elements
• Two counterfeit coins
• How to find many counterfeit coins?
• Five counterfeit coins
• A predetermined algorithm for detecting a counterfeit coin with a multi-arms balance
• Optimal detection of two counterfeit coins with two-arms balance.
• Optimal detection of a counterfeit coin with multi-arms balances
• Searching with lies
• Minimal average cost of searching for a counterfeit coin: restricted model
• On separating systems of a finite set
• Search with small sets in presence of a liar
• Searching games with errors -- fifty years of coping with liars