Dynamic Maintenance of Majority Information in Constant Time per Update

Gudmund Skovbjerg Frandsen
Sven Skyum

August 1995

Abstract:

We show how to maintain information about the existence of a majority colour in a set of elements under insertion and deletion of single elements using O(1) time and at most 4 equality tests on colours per update. No ordering information is used.

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.