Randomized Algorithms for Determining the Majority on Graphs

DOI10.1017/S0963548306007644zbMath1160.68687OpenAlexW2122000012MaRDI QIDQ3419763

Andrzej Pelc, Gianluca De Marco

Publication date: 7 February 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548306007644

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (7)

Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Majority problems of large query size ⋮ Computing majority via multiple queries ⋮ Determining majority in networks with local interactions and very small local memory ⋮ Randomized strategies for the plurality problem ⋮ On randomized algorithms for the majority problem ⋮ Randomized algorithms for the majority problem

This page was built for publication: Randomized Algorithms for Determining the Majority on Graphs