Determining Plurality

Laurent Alonso 1 Edward M. Reingold 2
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Given a set of $n$ elements, each of which is colored one of $c$ colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that $(c-1)(n-c)/2$ color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring $(0.775 c + 5.9)n + O(c^2)$ color comparisons for $c \geq 9$.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2008, 4 (3), pp.26:1,26:19. 〈10.1145/1367064.1367066〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00169184
Contributeur : Laurent Alonso <>
Soumis le : dimanche 2 septembre 2007 - 09:04:28
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Determining Plurality. ACM Transactions on Algorithms, Association for Computing Machinery, 2008, 4 (3), pp.26:1,26:19. 〈10.1145/1367064.1367066〉. 〈inria-00169184〉

Partager

Métriques

Consultations de la notice

226