3526 articles – 5249 references  [version française]

inria-00169184, version 1

Determining Plurality

Laurent Alonso () 1, Edward M. Reingold a, 2

ACM Transactions on Algorithms 4, 3 (2008) 26:1,26:19

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$.

  • a –  Illinois Institute of Technology, Chicago
  • 1:  ALICE (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2:  Department of Computer Science [IIT] (IIT CS)
  • Illinois Institute of Technology
  • Domain : Computer Science/Data Structures and Algorithms
 
  • inria-00169184, version 1
  • http://hal.inria.fr/inria-00169184
  • oai:hal.inria.fr:inria-00169184
  • From: Laurent Alonso <>
  • Submitted on: Sunday, 2 September 2007 09:04:28
  • Updated on: Thursday, 25 September 2008 16:18:17