Dynamic Maintenance of Majority Information in Constant Time per Update

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.