Publication

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Abhishek Methuku, Balázs Keszegh
2021
Journal Articles

Résumé

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(K-n) = n - b(n), where b(n) is the number of 1's in the binary representation of n.

Source officielle

https://infoscience.epfl.ch/entities/publication/3159e90a-35e3-43a5-b0b4-b5307fcecd92

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Adaptive majority problems for restricted query graphs and for weighted sets

Chattez avec Graph Search

Asynchronous Speedup in Decentralized Optimization

The Power of Two Matrices in Spectral Algorithms for Community Recovery

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al