Adaptive majority problems for restricted query graphs and for weighted sets

MaRDI QIDQ6621188zbMATH OpenFDO

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

Publication date 18 October 2024

Published in Acta Mathematica Universitatis Comenianae. New Series (Search for Journal in Brave)

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Adaptive majority problems for restricted query graphs and for weighted sets
• Majority and plurality problems
• Majority and plurality problems
• Finding a majority ball with majority answers
• Variants of the majority problem.

Cites work

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

This page was built for publication: Adaptive majority problems for restricted query graphs and for weighted sets

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