The plurality problem with three colors and more.

DOI10.1016/J.TCS.2004.12.035MaRDI QIDQ557833zbMATH OpenOpenAlexFDO

Authors Martin Aigner, Gianluca De Marco, Manuela Montangero

Publication date 30 June 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.12.035

zbMATH Keywords

Algorithm analysisCombinatorial searchGameMajority problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms (68W40) Search theory (90B40) Combinatorial games (91A46) Microeconomic theory (price theory and economic markets) (91B24)

Recommendations

• STACS 2004
• A plurality problem with three colors and query size three
• A note on the three color problem
• scientific article; zbMATH DE number 434910
• scientific article; zbMATH DE number 1500612
• scientific article; zbMATH DE number 5302772

Cites work

• Determining the majority
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• On computing majority by comparisons
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Search for a majority element
• STACS 2004
• The Average-Case Complexity of Determining the Majority
• The worst-case chip problem
• Variants of the majority problem.

Cited in

(16)

• Randomized strategies for the plurality problem
• Majority problems of large query size
• From discrepancy to majority
• A plurality problem with three colors and query size three
• Adaptive majority problems for restricted query graphs and for weighted sets
• Computing majority via multiple queries
• The majority game with an arbitrary majority
• Probabilistic strategies for the partition and plurality problems
• Determining plurality
• Searching for majority with k-tuple queries
• STACS 2004
• STACS 2005
• Computing and Combinatorics
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• How to play the majority game with a liar

This page was built for publication: The plurality problem with three colors and more.

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