Adaptive majority problems for restricted query graphs and for weighted sets

DOI10.1016/j.dam.2020.09.003zbMath1451.05076arXiv1903.08383OpenAlexW2986096732MaRDI QIDQ2208365

Balázs Keszegh, Dömötör Pálvölgyi, Dániel Gerbner, Balázs Patkós, Abhishek Methuku, Máté Vizer, Gábor Damásdi, Dániel Lenger, Gábor Wiener, Dániel T. Nagy, Gyula O. H. Katona

Publication date: 2 November 2020

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

Full work available at URL: https://arxiv.org/abs/1903.08383

zbMATH Keywords

vertex coloringcombinatorial searchadaptive searchmajority problem

Mathematics Subject Classification ID

Partitions of sets (05A18) Search theory (90B40) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Finding a non-minority ball with majority answers
• The plurality problem with three colors and more.
• Computing majority with triple queries
• Finding non-minority balls with majority and plurality queries
• On computing majority by comparisons
• On recognizing graph properties from adjacency matrices
• Variants of the majority problem.
• Majority problems of large query size
• From discrepancy to majority
• The quantum black-box complexity of majority
• Majority and plurality problems
• Computing majority via multiple queries
• Randomized Algorithms for Determining the Majority on Graphs
• Computing and Combinatorics
• Search for a majority element