Affordable Access

Publisher Website

Dynamic maintenance of majority information in constant time per update

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
63
Issue
2
Identifiers
DOI: 10.1016/s0020-0190(97)00100-2
Keywords
  • Data Structures
  • Analysis Of Algorithms

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.